快速排序非递归实现

前言：

为什么要实现快排非递归算法，不是已经有了递归算法了吗？

数据特别大时，快排递归会耗尽空间。因为计算机在实现递归时会调用系统的堆栈，这很消耗计算机内存资源，所以采用非递归算法的本质就是手动模拟系统的堆栈调用来降低computer资源的消耗。

步骤：

非递归实现快排本质就是用栈实现递归的操作。具体步骤如下：

1. 申请一个栈，存放排序数组的起始位置和终点位置。

2. 将整个数组的起始位置start和终点位置end进栈

3. 出栈数据，对出栈的数据进行排序，查找基准数据所在最终的位置pivot。

4. 判断起始位置start是否小于基准位置pivot-1，如果小于则将起始位置和pivot-1为终点位置进栈

5. 判断基准位置pivot+1 是否小于终点位置end,如果小于则将 pivot+1作为起始位置，end作为终点位置进栈

6. 判断栈是否为空，如果不为空则重复第三步，否则退出操作。

代码：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

//划分算法
int Partition(vector<int> & nums, int low, int high)
{
    int pivot = nums[low];
    while (low<high)
    {
        while(low<high && nums[high]>=pivot)
        {
            high--;
        }
        nums[low] = nums[high]; //将比枢轴值小的元素移到左边
        while(low<high && nums[low]<pivot)
        {
            low++;
        }
        nums[high] = nums[low]; //将比枢轴值大的元素移到右边
    }
    nums[low] = pivot;  //将枢轴值元素置于最终位置
    return low;
}


//非递归快排
void quickSort(vector<int> &nums, int start, int end)
{
    //手动利用栈来存储每次分块快排的起始点
	//栈非空时循环获取中轴入栈
    stack<int> s;
    if (start<end)
    {
        int pivot = Partition(nums,start,end);
        if (pivot-1>start)  //确保左分区存在
        {
            //将左分区端点入栈
            s.push(start);
            s.push(pivot-1);
        }
        if (pivot+1<end) //确保右分区存在
        {
            //将右分区端点入栈
            s.push(pivot+1);
            s.push(end);
        }
        while (!s.empty())
        {
            //得到其中一个分区的左右边界
            int r = s.top();
            s.pop();
            int l = s.top();
            s.pop();

            pivot = Partition(nums,l,r);
            if(pivot-1>l)
            {
                s.push(l);
                s.push(pivot-1);
            }
            if (pivot+1<r)
            {
                s.push(pivot+1);
                s.push(r);
            }
        }
    }
}

int main()
{
    vector<int> nums = {2,5,6,1,2,7,8,3,4,9};
    int n = nums.size();
    quickSort(nums,0,n-1);
    for (int num: nums)
    {
        cout << num << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

运行结果：