快速排序递归方法和非递归方法详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了快速排序递归方法和非递归方法详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

快速排序递归方法和非递归方法详解

1、快速排序（递归）

1.1、快速排序思想（递归）

快速排序（递归）是对数组进行拆解，也就是基于分治的思想。这里讨论将数组升序的情况：每次选出一个枢轴，在这部分数据中将小于该枢轴的元素放到枢轴的左边，大于枢轴的元素放到枢轴的右边，然后基于此次枢轴的位置，分成左右两个区间。再继续对此左右区间继续进行上述操作。每趟选出一个枢轴，每趟排序都可以将这次排序的枢轴放到最终位置。（看下面图解）
- 枢轴：即可以将序列分成两半的元素，枢轴大于左边序列，枢轴小于右边序列。

1.2、排序过程（递归）图解

每次选出一个枢轴（这里每次选的的最此次需要排序的左边元素），把这趟要排序的元素中小于枢轴的元素放到枢轴的左边，大于枢轴的元素放到枢轴的右边。
- 也就是right先走（最后left所指元素一定会比keyi所指元素小），从右往左走，找到比枢轴小的元素，就停下来。然后再left走，从左往右找，找到比枢轴大的元素，就停下来。然后交此时left和right对应的元素的值。left和right继续走，直到left == right。此时left所指元素一定小于keyi所指元素，将left所指元素余keyi所指元素互换，以确定此趟排序一个元素的最终位置pos。
确定好了枢轴的最终位置后，递归调用，把此次要排序的元素分成两组，左边一组（小于枢轴），右边一组（大于枢轴），对此左右两组继续采用上述方法。
- 这里仅画了部分图解，其他的过程自己考虑（和上述过程类似）。

1.3、快速排序（递归）代码

1.3.1、原始方法

先写出一趟排序的代码，即先选出此趟排序的枢轴，右边指针right先走，从右往左找到第一个小于枢轴的元素，就停下来。然后左边指针left再走，从左往右找到第一个大于枢轴的元素，就停下来。交换此时左右指针所指向的元素，然后继续上述过程（right先走），直到left == right。排序完将此枢轴放到整个数组的最终位置上。一趟排序的代码如下：

//一趟排序  ---  原始方法
int PartSort1(int *arr, int left, int right) {
    int midi = GetMid(arr, left, right);
    Swap(&arr[left], &arr[midi]);
    int keyi = left;
    while (left < right) {
        while (left < right && arr[right] >= arr[keyi]) {
            --right;
        }
        while (left < right && arr[left] <= arr[keyi]) {
            ++left;
        }
        Swap(&arr[left], &arr[right]);
    }
    //由于是右边先走，所以left处为最终枢轴元素的最终位置
    Swap(&arr[keyi], &arr[left]);
    return left;
}

这里我们注意到，这里有个GetMid函数，这个函数是干嘛的呢？其实，这个函数是用来优化递归版的快速排序的。这个函数可以用来对每趟排序的枢轴的取值更合理，即每趟取此趟排序的最前元素、最后元素、中间元素的中位数。这样可以非常有效防止对于一个基本有序或者已经有序的序列进行快速排序的时候递归深度太深。GetMid函数代码如下：

//取第一个、中间一个、最后一个元素中的中位数
int GetMid(int *arr, int left, int right) {
    int mid = (left + right) / 2;
    if (arr[mid] >= arr[left]) {
        if (arr[mid] >= arr[right]) {//mid处元素值最大
            if (arr[left] <= arr[right]) {//right处元素值第二大
                return right;
            } else {
                return left;//left处元素值第二大
            }
        } else {//right处元素值最大
            return mid;//mid处元素值第二大
        }
    } else {
        if (arr[left] >= arr[right]) {//left处元素值最大
            if (arr[mid] >= arr[right]) {
                return mid;//mid处元素值第二大
            } else {
                return right;//right处元素值第二大
            }
        }
    }
}

下面再介绍两种上述一趟排序的算法，分别是挖坑法和左右指针法。

1.3.2、挖坑法

挖坑法：首先在最左边枢轴元素处挖坑，用hole标记洞的位置，并且记录此元素值key，然后right先走，从右往左走，找到比key小的元素将其填补到左边的坑，并将此元素位置作为新的坑，然后再left走，找到比key大的元素将其填补到右边的坑，并将此元素位置作为新的坑。重复上述过程，直到left == right，再将已记录的枢轴填补到left位置上。最后洞的位置就是这趟排序枢轴的最终位置。

挖坑法部分图解：

挖坑法代码：

//一趟排序  ---  挖坑法
int PartSort2(int *arr, int left, int right) {
    int midi = GetMid(arr, left, right);
    Swap(&arr[left], &arr[midi]);
    int key = arr[left];
    int hole = left;//左边第一个坑位
    while (left < right) {
        //右边先走，找小，填到左边的坑，在右边形成新的坑位
        while (left < right && arr[right] >= key) {
            --right;
        }
        //右边坑位
        arr[hole] = arr[right];
        hole = right;
        //左边先走，找大，填到右边的坑，在左边形成新的坑位
        while (left < right && arr[left] <= key) {
            ++left;
        }
        //左边坑位
        arr[hole] = arr[left];
        hole = left;
    }
    arr[hole] = key;//最后一次坑填当前枢轴元素
    return hole;
}

1.3.3、左右指针法

左右指针法：取枢轴为最左边元素（keyi所指元素），定义两个指针pre和cur，pre用来记录大于枢轴的元素的前驱，cur用来从左往右找小于枢轴的元素，找到了就++pre，然后pre和cur所指元素交换（cur指向右边小于枢轴的元素，pre指向左边大于枢轴的元素），然后++cur，否则只需要++cur，pre不动。直到cur == right，就交换pre和keyi所指向的元素，即可确定此趟排序的最终枢轴位置pre。

左右指针法部分图解：

左右指针法代码：

//一趟排序  ---  左右指针法
int PartSort3(int *a, int left, int right) {
    int pre = left;
    int cur = left + 1;
    int keyi = left;
    while (cur <= right) {
        //cur找小于枢轴的元素，找到就++pre和cur元素交换，否则cur后移继续找
        if (a[cur] < a[keyi] && ++pre != cur) { //++pre != cur 防止自己和自己交换 这里pre已经++了
            Swap(&a[pre], &a[cur]);
        }
        ++cur;
    }
    Swap(&a[pre], &a[keyi]);
    return pre;
}

再来写整体的排序代码，即每趟选出一个枢轴元素后，就确定了它的最终位置，然后对此枢轴元素的左边序列排序，再对对此枢轴元素的右边序列排序。递归结束条件是只剩下一个元素（begin == end），或者begin > end，因为到这一步不需要排序了。

//快速排序 -- 递归方法
void QuickSort(int *arr, int begin, int end) {
    if (begin >= end)//只剩下一个元素，或者begin > end直接返回
        return;
    //先找到排序一趟后的枢轴元素的最终位置
    int pos = PartSort3(arr, begin, end);
    QuickSort(arr, begin, pos - 1);//对左边排序
    QuickSort(arr, pos + 1, end);//对右边排序
}

我们来想想，对于这个递归版的快速排序还能不能再优化？答案是肯定的。我们考虑一个问题，当排序到当前序列长度就为10左右，此序列是不是基本有序了，此时递归深度可能已经很深了。那基本有序了是不是可以考虑一下其他排序算法，不用递归的算法，可以降低递归深度，这里插入排序是最优选择。那么我们看下优化后的代码。其中判断此趟序列长度可以用end - begin。

//快速排序  -- 递归方法优化
void QuickSort(int *arr, int begin, int end) {
    if (begin >= end)//只剩下一个元素，或者begin > end直接返回
        return;
    if (end - begin <= 10) {
        //区间短短直接用插入排序，因为短区间此时基本有序了
        InsertSort(arr + begin, end - begin + 1);
    } else {
        //先找到排序一趟后的枢轴元素的最终位置
        int pos = PartSort3(arr, begin, end);
        QuickSort(arr, begin, pos - 1);//对左边排序
        QuickSort(arr, pos + 1, end);//对右边排序
    }
}

2、快速排序（非递归）

2.1、快速排序（非递归）思想

快速排序（非递归）和快速排序（递归）的思想类似，但是递归版的使用的系统栈，非递归版则是采用人工栈来模拟递归的系统栈。即还是采用分治法，每趟排序完把这趟的序列分成两部分。首先创建一个栈Stack，然后先把这整个要排序的序列的左右边界的下标压入栈中，这里采用先压左边边界下标left（也可以先压右边边界下标，出栈也得跟着变），然后压右边边界下标right。接下来就是对这个整个序列入栈出栈的操作了（排序）：取这次要排序的序列区间（取栈顶元素（左边界），再栈顶元素出栈，再取栈顶元素（右边界），再栈顶元素出栈），然后对这个区间的序列进行划分（确定这个序列的枢轴的最终位置pos）。然后判段这次枢轴的位置对于其左右区间是否还需要继续划分（pos和left、right比较，pos -1 > left，pos + 1 < right则继续划分），一直循环下去，直到栈空。

2.2、排序过程（非递归）图解

首先创建一个栈用来存每趟要排序的序列的左右边界
接下来就是出栈入栈了，可以得到一个区间，然后对该区间的序列进行划分来确定枢轴最终位置。
- 这里是部分图解，其他的过程自行思考（和这里图解过程类似）。

2.3、快速排序（非递归）代码

主要就是用人工栈模拟系统栈的压栈流程，为什么要使用非递归的方法？答案是因为系统栈递归调用可能导致栈的深度太深，而且系统栈递归调用保存的信息很多。快速排序（非递归）代码如下：
```
//快速排序 -- 非递归方法
void QuickSortNonR(int *arr, int begin, int end) {
    Stack st;
    STInit(&st);
    STPush(&st, end);
    STPush(&st, begin);//将此次排序的左右边界下标入栈
    while (!STEmpty(&st)) {
        int left = STTop(&st);
        STPop(&st);
        int right = STTop(&st);
        STPop(&st);
        int pos = PartSort2(arr, left, right);
        if (right > pos + 1) {
            STPush(&st, right);//右边排序
            STPush(&st, pos + 1);
        }
        if (left < pos - 1) {//有一个以上元素
            STPush(&st, pos - 1);//左边排序
            STPush(&st, left);
        }
    }
    STDestroy(&st);
}
```
- 这里每趟排序划分的代码和递归版的代码一样，就不再赘述。
- 时间复杂度：最坏情况：数组完全逆序，这时候需要递归n次（或者栈深度为n），共n个元素，所以最坏时间复杂度为O(n^2)。但是，极大多数情况是由于采用的是二分法，所以每趟排序的时间复杂度为O(logn)，又因为有n个元素，所以总的时间复杂度为O(nlogn)。
- 空间复杂度：由于需要递归或者使用栈，那么递归深度或者栈深度就是相当于需要的额外空间，最坏空间复杂度是O(n),这是在数组完全逆序的时候（使用GetMid函数能解决）。但是极大多数情况的空间复杂度是O(logn) <-- 采用二分法，相当于是n个结点的二叉树的高度。
- 算法稳定性：不稳定，考虑序列（2，2，1），排序后序列为（1，2，2），我们发现2的相对位置发生了变化，所以是不稳定的排序算法。