快速排序算法（#商汤# 手撕代码题）

基本思想：

• 通过下标指定数组arr当中要比较的元素范围[left, right]
• 在每一轮比较中，选一个基准值，将其余元素和基准值比较
• 假设基准值是arr[right]，定义两个变量i，j，初始时都指向left，用j遍历剩余元素，如果arr[j]小于基准值，那么将arr[i]和arr[j]交换，之后i递增
• j遍历完之后，此时i正处于一个枢纽pivot的位置，将arr[i]和arr[right]交换，完成一轮比较，将原数组划分为大于基准值和小于基准值的两部分
• 对各个部分重复上述过程

要求不用递归，写出基于迭代的方法，这里实现了两种：

基于递归的写法

int partition(vector &arr, int left, int right)
{
    int i = left;
    for(int j=left; j &arr, int left, int right)
{
    if(right <= left) return;
    int p = partition(arr, left, right);
    quickSort(arr, left, p-1);
    quickSort(arr, p+1, right);
}

基于迭代的写法：面试官提示用栈来实现

int partition(vector &arr, int left, int right)
{
    int i = left;
    for(int j=left; j &arr, int left, int right)
{
    if(right <= left) return;
    stack> s;
    s.push(make_pair(left, right));
    while(!s.empty())
    {
        auto x = s.top();
        s.pop();
        int p = partition(arr, x.first, x.second);
        if(x.second > p + 1) s.push(make_pair(p+1, x.second));
        if(p-1 > x.first) s.push(make_pair(x.first, p-1));
    }
}

测试了一下

int main()
{
    srand(0);
    for(int i=0; i<3; i++)
    {
        vector v;
        for(int j=0; j<5; j++)
        {
            int tmp = rand() % 10;
            cout << tmp << "t";
            v.push_back(tmp);
        }
        cout << "--> t";
        iterQuickSort(v, 0, v.size() - 1);
        // quickSort(v, 0, v.size() - 1);
        for (auto iter : v)
        {
            cout << iter << "t";
        }
        cout << "n";
    }
    return 0;
}