快速排序

您所在的位置：网站首页 › 快速排序的好处 › 快速排序

快速排序

2024-07-01 22:28| 来源: 网络整理| 查看: 265

本页面将简要介绍快速排序。

定义

快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称「快排」，是一种被广泛运用的排序算法。

基本原理与实现过程

快速排序的工作原理是通过分治的方式来将一个数组排序。

快速排序分为三个过程：

将数列划分为两部分（要求保证相对大小关系）；递归到两个子序列中分别进行快速排序；不用合并，因为此时数列已经完全有序。

和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数来当做两个子数列的分界。

之后，维护一前一后两个指针和，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针遇到了一个比小的数，那么可以交换和位置上的数，再把向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。

其实，快速排序没有指定应如何具体实现第一步，不论是选择的过程还是划分的过程，都有不止一种实现方法。

第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。

=== "C++1"

```cpp struct Range { int start, end; Range(int s = 0, int e = 0) { start = s, end = e; } }; template void quick_sort(T arr[], const int len) { if (len = range.end) continue; T mid = arr[range.end]; int left = range.start, right = range.end - 1; while (left < right) { while (arr[left] < mid && left < right) left++; while (arr[right] >= mid && left < right) right--; std::swap(arr[left], arr[right]); } if (arr[left] >= arr[range.end]) std::swap(arr[left], arr[range.end]); else left++; r[p++] = Range(range.start, left - 1); r[p++] = Range(left + 1, range.end); } } ```

=== "Python1"

```python def quick_sort(alist, first, last): if first >= last: return mid_value = alist[first] low = first high = last while low < high: while low < high and alist[high] >= mid_value: high -= 1 alist[low] = alist[high] while low < high and alist[low] < mid_value: low += 1 alist[high] = alist[low] alist[low] = mid_value quick_sort(alist, first, low - 1) quick_sort(alist, low + 1, last) ``` 性质稳定性

快速排序是一种不稳定的排序算法。

时间复杂度

快速排序的最优时间复杂度和平均时间复杂度为，最坏时间复杂度为。

对于最优情况，每一次选择的分界值都是序列的中位数，此时算法时间复杂度满足的递推式为，由主定理，。

对于最坏情况，每一次选择的分界值都是序列的最值，此时算法时间复杂度满足的递推式为，累加可得。

对于平均情况，每一次选择的分界值可以看作是等概率随机的。

证明

下面我们来证明这种情况下算法的时间复杂度是。

引理 1：当对个元素的数组进行快速排序时，假设在划分元素时总共的比较次数为，则快速排序的时间复杂度是。

由于在每次划分元素的过程中，都会选择一个元素作为分界，所以划分元素的过程至多发生次。又由于划分元素的过程中比较的次数和其他基础操作的次数在一个数量级，所以总时间复杂度是的。

设为原数组中第小的数，定义为，是一个取值为或者的离散随机变量表示在排序过程中是否和发生比较。

显然每次选取的分界值是不同的，而元素只会和分界值比较，所以总比较次数

由期望的线性性，

和比较

引理 2：和比较的充要条件是或是集合中第一个被选中的分界值。

先证必要性，即若和都不是集合中第一个被选中的分界值，则不和比较。

若和都不是集合中第一个被选中的分界值，则一定存在一个满足，使得是中第一个被选中的分界值。在以为分界值的划分中，和被划分到数组的两个不同的子序列中，所以之后和一定不会比较。又因为元素只和分界值比较，所以和在此次划分前和划分中没有比较。所以不和比较。

再证充分性，即若或是集合中第一个被选中的分界值，则和比较。

不失一般地，假设是集合中第一个被选中的分界值。由于中没有其他数选为分界值，所以中的元素都在数组的同一子序列中。在以为分界值的划分中，和当前子序列中所有元素都进行了比较，所以和进行了比较。

考虑计算和比较。在中某个元素被选为分界值之前，中的元素都在数组的同一子序列中。所以中每个元素都会被等可能地第一个被选为分界值。由于中有个元素，由引理 2，

和比较或是集合中第一个被选中的分界值

所以

和比较

由此，快速排序的期望时间复杂度为。

在实践中，几乎不可能达到最坏情况，而快速排序的内存访问遵循局部性原理，所以多数情况下快速排序的表现大幅优于堆排序等其他复杂度为的排序算法。2

优化朴素优化思想

如果仅按照上文所述的基本思想来实现快速排序（或者是直接照抄模板）的话，那大概率是通不过 P1177【模板】快速排序这道模板的。因为有毒瘤数据能够把朴素的快速排序卡成。

所以，我们需要对朴素快速排序思想加以优化。较为常见的优化思路有以下三种3。

通过三数取中（即选取第一个、最后一个以及中间的元素中的中位数）的方法来选择两个子序列的分界元素（即比较基准）。这样可以避免极端数据（如升序序列或降序序列）带来的退化；当序列较短时，使用插入排序的效率更高；每趟排序后，将与分界元素相等的元素聚集在分界元素周围，这样可以避免极端数据（如序列中大部分元素都相等）带来的退化。

下面列举了几种较为成熟的快速排序优化方式。

三路快速排序定义

三路快速排序（英语：3-way Radix Quicksort）是快速排序和基数排序的混合。它的算法思想基于荷兰国旗问题的解法。

过程

与原始的快速排序不同，三路快速排序在随机选取分界点后，将待排数列划分为三个部分：小于、等于以及大于。这样做即实现了将与分界元素相等的元素聚集在分界元素周围这一效果。

性质

三路快速排序在处理含有多个重复值的数组时，效率远高于原始快速排序。其最佳时间复杂度为。

实现

三路快速排序实现起来非常简单，下面给出了一种三路快排的 C++ 实现。

=== "C++"

```cpp // 模板的 T 参数表示元素的类型，此类型需要定义小于（= r: return random_index = random.randint(l, r) pivot = arr[random_index] arr[l], arr[random_index] = arr[random_index], arr[l] i = l + 1 j = l k = r + 1 while i < k: if arr[i] < pivot: arr[i], arr[j + 1] = arr[j + 1], arr[i] j += 1 i += 1 elif arr[i] > pivot: arr[i], arr[k - 1] = arr[k - 1], arr[i] k -= 1 else: i += 1 arr[l], arr[j] = arr[j], arr[l] quick_sort(arr, l, j - 1) quick_sort(arr, k, r) ``` 内省排序定义

内省排序（英语：Introsort 或 Introspective sort）4是快速排序和堆排序的结合，由 David Musser 于 1997 年发明。内省排序其实是对快速排序的一种优化，保证了最差时间复杂度为。

性质

内省排序将快速排序的最大递归深度限制为，超过限制时就转换为堆排序。这样既保留了快速排序内存访问的局部性，又可以防止快速排序在某些情况下性能退化为。

实现

从 2000 年 6 月起，SGI C++ STL 的 stl_algo.h 中 sort() 函数的实现采用了内省排序算法。

线性找第 k 大的数

在下面的代码示例中，第大的数被定义为序列排成升序时，第个位置上的数（编号从 0 开始）。

找第大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第大的位置的元素。这样做的时间复杂度是，对于这个问题来说很不划算。

我们可以借助快速排序的思想解决这个问题。考虑快速排序的划分过程，在快速排序的「划分」结束后，数列被分成了和，此时可以按照左边元素的个数（）和的大小关系来判断是只在左边还是只在右边递归地求解。

和快速排序一样，该方法的时间复杂度依赖于每次划分时选择的分界值。如果采用随机选取分界值的方式，可以证明在期望意义下，程序的时间复杂度为。

实现（C++）改进：中位数中的中位数

中位数中的中位数（英文：Median of medians），提供了一种确定性的选择划分过程中分界值的方法，从而能够让找第大的数算法在最坏情况下也能实现线性时间复杂度。

该算法的流程如下：

将整个序列划分为组，每组元素数不超过 5 个；寻找每组元素的中位数（因为元素个数较少，可以直接使用插入排序等算法）。找出这组元素中位数中的中位数。将该元素作为前述算法中每次划分时的分界值即可。时间复杂度证明

下面将证明，该算法在最坏情况下的时间复杂度为。设为问题规模为时，解决问题需要的计算量。

先分析前两步——划分与寻找中位数。由于划分后每组内的元素数量非常少，可以认为寻找一组元素的中位数的时间复杂度为。因此找出所有组元素中位数的时间复杂度为。

接下来分析第三步——递归过程。这一步进行了两次递归调用：第一次是寻找各组中位数中的中位数，需要的开销显然为，第二次是进入分界值的左侧部分或右侧部分。根据我们选取的划分元素，有组元素的中位数小于分界值，这几组元素中，比中位数还小的元素也一定比分界值要小，从而整个序列中小于分界值的元素至少有个。同理，整个序列中大于分界值的元素也至少有个。因此，分界值的左边或右边至多有个元素，这次递归的时间开销的上界为。

综上，我们可以列出这样的不等式：

假设在问题规模足够小时成立。根据定义，此时有，其中为一正常数。将不等式右边的所有进行代换：

到这里我们就证明了，该算法在最坏情况下也具有的时间复杂度。

参考资料与注释 Footnotes

算法实现/排序/快速排序 - 维基教科书，自由的教学读本 ↩ ↩2 ↩3

C++ 性能榨汁机之局部性原理 - I'm Root lee ! ↩

三种快速排序以及快速排序的优化 ↩

introsort ↩

【本文地址】

公司简介

联系我们