快速排序的堆栈实现方法， C++ 版

1.快排序理论：
快速排序是一种平均时间性能非常好的方法。一般排序算法，每次循环之后只能减少一个数据量因此复杂度是O(N2)，而快排序是选定基准元素，一般取第一个，每次安排完一个数据后还能将其余数据分成一组比它大和一组比它小的两组数据，按此方法，再依次分别对分好类的数据进行排序操作，下面以一组数据举例。
int arrIn[] = {36,34,67,44,8,6,9,45,87}
以第一项36为基准元素，
36 [ ], 34, 67, 44, 8, 6, 9, 45, 87
                                                 <--
36 [ 9], 34, 67, 44, 8, 6, [ ], 45, 87
            -->
36 [ 9], 34, [ ], 44, 8, 6, [ 67], 45, 87
                                        <--
36 [ 9], 34, [6 ], 44, 8, [ ], [ 67], 45, 87
                    -->
36 [ 9], 34, [6 ], [ ], 8, [ 44], [ 67], 45, 87
                                    <--
36 [ 9], 34, [6 ], [8 ], [ ], [ 44], [ 67], 45, 87
                                      --><--
左右指针相遇完成一次排序，将基准元素放到空余位置
第一次排序后的list为：
9 ，34 ，6 ，8 ，36 ，44 ，67 ，45 ，87
第二次从左半部分开始：
8 ，6 ，9 ，34
第三次从左半部开始
6 ，8 ，9 ，34
第四次从36的右半部开始，类似上面操作
。。。
最终排序结果
6 ，8 ，9 ，34 ，36 ，44 ，45 ，67 ，87

2.基于堆栈实现的快排序代码：
堆栈操作实现：

#ifndef _CPPSTACK_H_
#define _CPPSTACK_H_
/****** include *******/
#include <iostream>
#include <stdio.h>
/****** define *********/
/****** variable ********/
struct Item
{
    int data;
    Item* p_next;
};

class CPPStack
{
public:
    CPPStack();
    CPPStack(const CPPStack & otherStack);//constructor reset
    CPPStack operator = (const CPPStack & otherStack);//'=' reset
    void push(int x);//in stack
    bool pop(int &x);//out stack
    bool isEmpty();
    void clearStack();
    int sizeStack();
    void printStack();
    ~CPPStack();
public:
    Item* p_top;//stack top
};
/****** function *******/
#endif // _CPPSTACK_H_

/*****************************
filename: CPPStack.cpp
description: realize stack operate in CPP
                like, stack struct; push; pop; isEmpty; clear;
                size; print
author: warrior mail:[e-mail]
date:2016-1-31
log:
*****************************/

/****** include *******/
#include "CPPStack.h"
using namespace std;
/****** define *********/
/****** variable ********/
/****** function *******/
/****************
description: stack operate class constructor
input:
    none
output:
    none
****************/
CPPStack::CPPStack()
{
    p_top = NULL;
}
CPPStack::CPPStack(const CPPStack & otherStack)
{
    *this = otherStack;
}

/****************
description: reset operator '=' for stack
input:
    const CPPStack otherStack : the right value of '='
output:
    CPPStack
****************/
CPPStack CPPStack::operator=(const CPPStack & otherStack)
{
    CPPStack temporaryStack;
    Item* copyElement = otherStack.p_top;

    while(copyElement)
    {
        temporaryStack.push(copyElement->data);
        copyElement = copyElement->p_next;
    }

    copyElement = temporaryStack.p_top;

    while(copyElement)
    {
        this->push(copyElement->data);
        copyElement = copyElement->p_next;
    }
    return *this;
}

/****************
description: insert one element into stack
input:
    const int x : the value to be insert into stack
output:
    none
****************/
void CPPStack::push(const int x)
{
    Item *temporaryElement;
    temporaryElement = new Item;
    temporaryElement->data = x;
    if(this->p_top != NULL)
    {
        temporaryElement->p_next = this->p_top;
        this->p_top = temporaryElement;
    }
    else
    {
        this->p_top = temporaryElement;
        this->p_top->p_next = NULL;
    }
    printf("push stack data: %d \n", temporaryElement->data);
}
/****************
description: get one element from stack
input:
    const int & x : storage the value get from stack into x
output:
    ture:success
    false:error
****************/
bool CPPStack::pop(int &x)
{
    if(this->p_top != NULL)
    {

        x = this->p_top->data;
        this->p_top = this->p_top->p_next;
        printf("pop stack data: %d \n", x);
        return true;
    }
    else
    {
        return false;
    }
}
/****************
description: judge whether stack empty
input:
    none
output:
    ture:not empty
    false:empty
****************/
bool CPPStack::isEmpty()
{
    if(this->p_top != NULL)
    {return true;}
    else
    {return false;}
}
/****************
description: clear all element of stack
input:
    none
output:
    none
****************/
void CPPStack::clearStack()
{
    Item* tempElement;
    while(this->p_top)
    {
        tempElement = this->p_top;
        this->p_top = this->p_top->p_next;
        delete tempElement;
    }
}
/****************
description: test the size of stack
input:
    none
output:
    int lenght
****************/
int CPPStack::sizeStack()
{
    int counter = 0;
    Item* tempElement;
    tempElement = this->p_top;
    while(tempElement)
    {
        counter++;
        tempElement = tempElement->p_next;
    }
    return counter;
}
/****************
description: print all elements of stack
input:
    none
output:
    none
****************/
void CPPStack::printStack()
{
    Item* tempElement = this->p_top;
    while(tempElement)
    {
        printf("  %d\n",tempElement->data);
        tempElement = tempElement->p_next;
    }
}

CPPStack::~CPPStack()
{
    Item* tempElement;
    while(this->p_top)
    {
        tempElement = this->p_top;
        this->p_top = this->p_top->p_next;
        delete tempElement;
    }
}

快速排序算法实现：

/*****************************
filename: quickSort.cpp
description: permutation a list of integers in O(1) and no recursion
author: warrior mail:[e-mail]
date:2016-1-30
log:
*****************************/

/****** include *******/
#include "quickSort.h"
#include "CPPStack.h"
using namespace std;
/****** define *********/
/****** variable ********/

/****** function *******/
/****************
description: permutation a list of integers in O(1) and no recursion
input:
    int* arrIN : the in put interger array
    int arrLength : length of array "arrIN"
output:
    0:run error
    1:run success
****************/
bool quickSort(int* arrIN, int arrLength)
{
    int supportElement;
    int emptySign = 0;
    int lowRecord = 0;
    int highRecord = 0;
    int temp;
    int lowSign = 0;
    int highSign = arrLength-1;
    CPPStack quickSortStack;
    if(arrIN==NULL)
    {return 0;}

    quickSortStack.push(arrLength-1);
    quickSortStack.push(0);

    while(quickSortStack.isEmpty())
    {
        quickSortStack.pop(lowSign);
        quickSortStack.pop(highSign);

        lowRecord = lowSign;
        highRecord = highSign;
        emptySign = lowSign;
        supportElement = arrIN[emptySign];

        if(highSign-lowSign>1)
        {
            while(lowSign<highSign)
            {
                //search from high
                while((lowSign<highSign) && (supportElement<=arrIN[highSign]))
                {
                    highSign--;
                    //printf(", %d\n", highSign);
                }
                if(lowSign<highSign)
                {
                    arrIN[emptySign] = arrIN[highSign];
                    emptySign = highSign;
                }
                //search from low
                while((lowSign<highSign) && (supportElement>=arrIN[lowSign]))
                {
                    lowSign++;
                    //printf(", %d\n", lowSign);
                }
                if(lowSign<highSign)
                {
                    arrIN[emptySign] = arrIN[lowSign];
                    emptySign = lowSign;
                }
            }
            arrIN[emptySign] = supportElement;
            printf("the sorting line:\n");
            for(int i = 0; i<arrLength; i++)
            {
                printf(", %d", arrIN[i]);
            }
            printf("\n");
            //push high
            quickSortStack.push(highRecord);
            if(lowSign == highRecord)
                quickSortStack.push(lowSign);
            else
                quickSortStack.push(lowSign+1);
            //push low
            if(lowSign == lowRecord)
                quickSortStack.push(lowSign);
            else
                quickSortStack.push(lowSign-1);
            quickSortStack.push(lowRecord);

        }
        else
        {
            if(arrIN[lowSign]>arrIN[highSign])
            {
                temp = arrIN[highSign];
                arrIN[highSign] = arrIN[lowSign];
                arrIN[lowSign] = temp;
            }
        }
    }
    printf("the sorted line:\n");
    for(int i = 0; i<arrLength; i++)
    {
        printf(", %d", arrIN[i]);
    }
    printf("\n");
}

#ifndef _QUICKSORT_H_
#define _QUICKSORT_H_
/****** include *******/
#include <iostream>
#include <stdio.h>
/****** define *********/
/****** variable ********/

/****** function *******/
bool quickSort(int* arrIN, int arrLength);
#endif // _QUICKSORT_H_

主函数：

#include "CPPStack.h"
#include "quickSort.h"


using namespace std;

int main()
{
    int arrIn[] = {36,34,67,44,8,6,9,45,87};
    quickSort(arrIn, sizeof(arrIn)/sizeof(int));

    return 0;
}

3.总结
这次实现代码过程中遇到的问题
（1）遇到“segmentation fault”错误，段错误，经过查资料，知道是指针误操作导致，错误原因：程序中指针没有初始化就进行相应操作
（2）压栈操作压入数据异常，此处也属于指针操作错误，指针操作前应先初始化，C++ 用new关键字， C里面用malloc函数
            使用实例：
            new:
            int *p = new int(10);
            注意使用结束时使用delete释放：
            delete p;
            malloc:
            void *malloc(long NumBytes)
            char *charList = (char *)malloc(100 * sizeof(char));
            注意使用结束时，使用free释放：
            free(charList);
（3）快速排序是一种不稳定排序方法