非递归的快速排序实现

     快速排序法 (quick sort)是运用分治思想(divide and conquer)对一个数组进行排序的比较排序算法。它主要思想是：以某个数为轴，将这个数组划分成两部分：不大于这个轴的一部分和大于这个轴的一部分；然后在分别对剩下的两部分进行同样的操作；一直分下去，直到每部分只有一个元素位置为止。

    如何划分成两部分？严蔚敏的《数据结构》和《算法导论》有两种不同的具体实现

    【严】的描述如下：设置两个数组下标low,high，low从前向后移动，high从后往前移动，保证low之前的部分都是不大于轴，high之后的部分都是大于轴; 每次low找到一个大于轴的元素，high找到一个不大于轴的元素，交换这两个元素的位置。如果low等于high了，则把这个位置和轴所在地位置交换。

     《算法导论》上的划分是这样的：也是给定两个数组下标i和j，i和j都从前往后移动； 保证i之前的部分都不大于轴，j之后的部分(包含j)都未知； j向后滑动中如果某个元素不大于轴，这把这个元素的位置和i交换，并且i向前移动一个位置. 当j到达末尾后，把轴的位置与i位置上的元素交换，i即为分界点。

 

    如何非递归实现？一般书上的快速排序法都是用递归实现的，递归是编译器自动用栈来实现的。当递归层次比较深时，需要占用比较大的进程栈空间，还有进程栈溢出的危险。很多时候将递归转化为非递归算法，更省时间和空间。

    其实原理很简单，即自己用栈来模拟递归的过程。每次从栈顶取出一部分做划分后，都把新的两部分的起始位置分别入栈。

 

   c++算法实现如下(采用《算法导论》上的方法)：
   

#ifndef MAX_STACK_DEPTH
#define MAX_STACK_DEPTH 1000
#endif
template <typename T>
void NonrecursiveQuickSort(T arr[], size_t size)
{
    //  typedef vector<int> Stack_t;
    int stack[MAX_STACK_DEPTH];
    int top = 0;
    int low,high,i,j,pivot;
    T temp;
	//首先把整个数组入栈
    stack[top++] = size-1;
    stack[top++] = 0;
    while(top != 0)
    {
		//取出栈顶元素，进行划分
        low = stack[--top];
        high = stack[--top];
        pivot = high;   //将最后一个元素作为轴
        i = low;       //保证i之前的元素的不大于轴
        //j从前往后滑动
        for(j=low; j < high; j++)
        {
            //如果碰到某个元素不大于轴，则与arr[i]交换
            if(arr[j]<=arr[pivot])
            {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                i++;
            }
        }
		//i为分界点，交换arr[i]和轴
        if(i != pivot)
        {
            /*swap arr[i] and arr[pivot]*/
            temp = arr[i];
            arr[i] = arr[pivot];
            arr[pivot] = temp;
        }
		//判断小于轴的部分元素如果多于一个的话, 则入栈
        if(i-low > 1)
        {
            stack[top++] = i-1;
            stack[top++] = low;
        }
		//判断大于轴的部分元素如果多于一个的话, 则入栈
        if(high-i > 1)
        {
            stack[top++] = high;
            stack[top++] = i+1;
        }
    }
}