快速排序本页面将简要介绍快速排序．
定义快速排序（英语：Quicksort），又称分区交换排序（英语：partition-exchange sort），简称「快排」，是一种被广泛运用的排序算法．
基本原理与实现过程快速排序的工作原理是通过 分治 的方式来将一个数组排序．
快速排序分为三个过程：
将数列划分为两部分（要求保证相对大小关系）；递归到两个子序列中分别进行快速排序；不用合并，因为此时数列已经完全有序．和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系．具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数．为了保证平均时间复杂度，一般是随机选择一个数 𝑚m 来当做两个子数列的分界．
之后，维护一前一后两个指针 𝑝p 和 𝑞q，依次考虑当前的数是否放在了应该放的位置（前还是后）．如果当前的数没放对，比如说如果后面的指针 𝑞q 遇到了一个比 𝑚m 小的数，那么可以交换 𝑝p 和 𝑞q 位置上的数，再把 𝑝p 向后移一位．当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇．
其实，快速排序没有指定应如何具体实现第一步，不论是选择 𝑚m 的过程还是划分的过程，都有不止一种实现方法．
第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了．
C++Python4非递归实现4递归实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30struct 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 <= 0) return;
Range r[len];
int p = 0;
r[p++] = Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= 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);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26template
int Partition(T A[], int low, int high) {
int pivot = A[low];
while (low < high) {
while (low < high && pivot <= A[high]) --high;
A[low] = A[high];
while (low < high && A[low] <= pivot) ++low;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
template
void QuickSort(T A[], int low, int high) {
if (low < high) {
int pivot = Partition(A, low, high);
QuickSort(A, low, pivot - 1);
QuickSort(A, pivot + 1, high);
}
}
template
void QuickSort(T A[], int len) {
QuickSort(A, 0, len - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def 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)
性质稳定性快速排序是一种不稳定的排序算法．
时间复杂度快速排序的最优时间复杂度和平均时间复杂度为 𝑂(𝑛log𝑛)O(nlogn)，最坏时间复杂度为 𝑂(𝑛2)O(n2)．
对于最优情况，每一次选择的分界值都是序列的中位数，此时算法时间复杂度满足的递推式为 𝑇(𝑛) =2𝑇(𝑛2) +Θ(𝑛)T(n)=2T(n2)+Θ(n)，由主定理，𝑇(𝑛) =Θ(𝑛log𝑛)T(n)=Θ(nlogn)．
对于最坏情况，每一次选择的分界值都是序列的最值，此时算法时间复杂度满足的递推式为 𝑇(𝑛) =𝑇(𝑛 −1) +Θ(𝑛)T(n)=T(n−1)+Θ(n)，累加可得 𝑇(𝑛) =Θ(𝑛2)T(n)=Θ(n2)．
对于平均情况，每一次选择的分界值可以看作是等概率随机的．
证明 下面我们来证明这种情况下算法的时间复杂度是 𝑂(𝑛log𝑛)O(nlogn)．
引理 1： 当对 𝑛n 个元素的数组进行快速排序时，假设在划分元素时总共的比较次数为 𝑋X，则快速排序的时间复杂度是 𝑂(𝑛 +𝑋)O(n+X)．
由于在每次划分元素的过程中，都会选择一个元素作为分界，所以划分元素的过程至多发生 𝑛n 次．又由于划分元素的过程中比较的次数和其他基础操作的次数在一个数量级，所以总时间复杂度是 𝑂(𝑛 +𝑋)O(n+X) 的．
设 𝑎𝑖ai 为原数组中第 𝑖i 小的数，定义 𝐴𝑖,𝑗Ai,j 为 {𝑎𝑖,𝑎𝑖+1,…,𝑎𝑗}{ai,ai+1,…,aj}，𝑋𝑖,𝑗Xi,j 是一个取值为 00 或者 11 的离散随机变量表示在排序过程中 𝑎𝑖ai 是否和 𝑎𝑗aj 发生比较．
显然每次选取的分界值是不同的，而元素只会和分界值比较，所以总比较次数
𝑋=𝑛−1∑𝑖=1𝑛∑𝑗=𝑖+1𝑋𝑖,𝑗X=∑i=1n−1∑j=i+1nXi,j 由期望的线性性，
𝐸[𝑋]=𝐸[𝑛−1∑𝑖=1𝑛∑𝑗=𝑖+1𝑋𝑖,𝑗]=𝑛−1∑𝑖=1𝑛∑𝑗=𝑖+1𝐸[𝑋𝑖,𝑗]=𝑛−1∑𝑖=1𝑛∑𝑗=𝑖+1𝑃(𝑎𝑖 和 𝑎𝑗 比较)E[X]=E[∑i=1n−1∑j=i+1nXi,j]=∑i=1n−1∑j=i+1nE[Xi,j]=∑i=1n−1∑j=i+1nP(ai 和 aj 比较) 引理 2： 𝑎𝑖ai 和 𝑎𝑗aj 比较的充要条件是 𝑎𝑖ai 或 𝑎𝑗aj 是集合 𝐴𝑖,𝑗Ai,j 中第一个被选中的分界值．
先证必要性，即若 𝑎𝑖ai 和 𝑎𝑗aj 都不是集合 𝐴𝑖,𝑗Ai,j 中第一个被选中的分界值，则 𝑎𝑖ai 不和 𝑎𝑗aj 比较．
若 𝑎𝑖ai 和 𝑎𝑗aj 都不是集合 𝐴𝑖,𝑗Ai,j 中第一个被选中的分界值，则一定存在一个 𝑥x 满足 𝑖 <𝑥 <𝑗i 再证充分性，即若 𝑎𝑖ai 或 𝑎𝑗aj 是集合 𝐴𝑖,𝑗Ai,j 中第一个被选中的分界值，则 𝑎𝑖ai 和 𝑎𝑗aj 比较． 不失一般地，假设 𝑎𝑖ai 是集合 𝐴𝑖,𝑗Ai,j 中第一个被选中的分界值．由于 𝐴𝑖,𝑗Ai,j 中没有其他数选为分界值，所以 𝐴𝑖,𝑗Ai,j 中的元素都在数组的同一子序列中．在以 𝑎𝑖ai 为分界值的划分中，𝑎𝑖ai 和当前子序列中所有元素都进行了比较，所以 𝑎𝑖ai 和 𝑎𝑗aj 进行了比较． 考虑计算 𝑃(𝑎𝑖 和 𝑎𝑗 比较)P(ai 和 aj 比较)．在 𝐴𝑖,𝑗Ai,j 中某个元素被选为分界值之前，𝐴𝑖,𝑗Ai,j 中的元素都在数组的同一子序列中．所以 𝐴𝑖,𝑗Ai,j 中每个元素都会被等可能地第一个被选为分界值．由于 𝐴𝑖,𝑗Ai,j 中有 𝑗 −𝑖 +1j−i+1 个元素，由引理 2， 𝑃(𝑎𝑖和𝑎𝑗比较)=𝑃(𝑎𝑖或𝑎𝑗是集合𝐴𝑖,𝑗中第一个被选中的分界值)=2𝑗−𝑖+1P(ai和aj比较)=P(ai或aj是集合Ai,j中第一个被选中的分界值)=2j−i+1 所以 𝐸[𝑋]=𝑛−1∑𝑖=1𝑛∑𝑗=𝑖+1𝑃(𝑎𝑖 和 𝑎𝑗 比较)=𝑛−1∑𝑖=1𝑛∑𝑗=𝑖+12𝑗−𝑖+1=𝑛−1∑𝑖=1𝑛−𝑖+1∑𝑘=22𝑘=𝑛−1∑𝑖=1𝑂(log𝑛)=𝑂(𝑛log𝑛)E[X]=∑i=1n−1∑j=i+1nP(ai 和 aj 比较)=∑i=1n−1∑j=i+1n2j−i+1=∑i=1n−1∑k=2n−i+12k=∑i=1n−1O(logn)=O(nlogn) 由此，快速排序的期望时间复杂度为 𝑂(𝑛log𝑛)O(nlogn)． 在实践中，几乎不可能达到最坏情况，而快速排序的内存访问遵循局部性原理，所以多数情况下快速排序的表现大幅优于堆排序等其他复杂度为 𝑂(𝑛log𝑛)O(nlogn) 的排序算法．1 优化朴素优化思想如果仅按照上文所述的基本思想来实现快速排序（或者是直接照抄模板）的话，那大概率是通不过 P1177【模板】快速排序 这道模板的．因为有毒瘤数据能够把朴素的快速排序卡成 𝑂(𝑛2)O(n2)． 所以，我们需要对朴素快速排序思想加以优化．较为常见的优化思路有以下三种2． 通过 三数取中（即选取第一个、最后一个以及中间的元素中的中位数） 的方法来选择两个子序列的分界元素（即比较基准）．这样可以避免极端数据（如升序序列或降序序列）带来的退化；当序列较短时，使用 插入排序 的效率更高；每趟排序后，将与分界元素相等的元素聚集在分界元素周围，这样可以避免极端数据（如序列中大部分元素都相等）带来的退化．下面列举了几种较为成熟的快速排序优化方式． 三路快速排序定义三路快速排序（英语：3-way Radix Quicksort）是快速排序和 基数排序 的混合．它的算法思想基于 荷兰国旗问题 的解法． 过程与原始的快速排序不同，三路快速排序在随机选取分界点 𝑚m 后，将待排数列划分为三个部分：小于 𝑚m、等于 𝑚m 以及大于 𝑚m．这样做即实现了将与分界元素相等的元素聚集在分界元素周围这一效果． 性质三路快速排序在处理含有多个重复值的数组时，效率远高于原始快速排序．其最佳时间复杂度为 𝑂(𝑛)O(n)． 实现三路快速排序实现起来非常简单，下面给出了一种三路快排的 C++ 实现． C++Python4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25// 模板的 T 参数表示元素的类型，此类型需要定义小于（<）运算 template // arr 为需要被排序的数组，len 为数组长度 void quick_sort(T arr[], const int len) { if (len <= 1) return; // 随机选择基准（pivot） const T pivot = arr[rand() % len]; // i：当前操作的元素下标 // arr[0, j)：存储小于 pivot 的元素 // arr[k, len)：存储大于 pivot 的元素 int i = 0, j = 0, k = len; // 完成一趟三路快排，将序列分为： // 小于 pivot 的元素 | 等于 pivot 的元素 | 大于 pivot 的元素 while (i < k) { if (arr[i] < pivot) swap(arr[i++], arr[j++]); else if (pivot < arr[i]) swap(arr[i], arr[--k]); else i++; } // 递归完成对于两个子序列的快速排序 quick_sort(arr, j); quick_sort(arr + k, len - k); } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22def quick_sort(arr, l, r): if l >= 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）3是快速排序和 堆排序 的结合，由 David Musser 于 1997 年发明．内省排序其实是对快速排序的一种优化，保证了最差时间复杂度为 𝑂(𝑛log𝑛)O(nlogn)． 性质内省排序将快速排序的最大递归深度限制为 ⌊log2𝑛⌋⌊log2n⌋，超过限制时就转换为堆排序．这样既保留了快速排序内存访问的局部性，又可以防止快速排序在某些情况下性能退化为 𝑂(𝑛2)O(n2)． 实现从 2000 年 6 月起，SGI C++ STL 的 stl_algo.h 中 sort() 函数的实现采用了内省排序算法． 线性找第 k 大的数在下面的代码示例中，第 𝑘k 大的数被定义为序列排成升序时，第 𝑘k 个位置上的数（编号从 0 开始）． 找第 𝑘k 大的数（K-th order statistic），最简单的方法是先排序，然后直接找到第 𝑘k 大的位置的元素．这样做的时间复杂度是 𝑂(𝑛log𝑛)O(nlogn)，对于这个问题来说很不划算． 我们可以借助快速排序的思想解决这个问题．考虑快速排序的划分过程，在快速排序的「划分」结束后，数列 𝐴𝑝⋯𝐴𝑟Ap⋯Ar 被分成了 𝐴𝑝⋯𝐴𝑞Ap⋯Aq 和 𝐴𝑞+1⋯𝐴𝑟Aq+1⋯Ar，此时可以按照左边元素的个数（𝑞 −𝑝 +1q−p+1）和 𝑘k 的大小关系来判断是只在左边还是只在右边递归地求解． 和快速排序一样，该方法的时间复杂度依赖于每次划分时选择的分界值．如果采用随机选取分界值的方式，可以证明在期望意义下，程序的时间复杂度为 𝑂(𝑛)O(n)． 实现（C++） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31// 模板的 T 参数表示元素的类型，此类型需要定义小于（<）运算 template // arr 为查找范围数组，rk 为需要查找的排名（从 0 开始），len 为数组长度 T find_kth_element(T arr[], int rk, const int len) { if (len <= 1) return arr[0]; // 随机选择基准（pivot） const T pivot = arr[rand() % len]; // i：当前操作的元素下标 // arr[0, j)：存储小于 pivot 的元素 // arr[k, len)：存储大于 pivot 的元素 int i = 0, j = 0, k = len; // 完成一趟三路快排，将序列分为： // 小于 pivot 的元素 ｜ 等于 pivot 的元素 ｜ 大于 pivot 的元素 while (i < k) { if (arr[i] < pivot) swap(arr[i++], arr[j++]); else if (pivot < arr[i]) swap(arr[i], arr[--k]); else i++; } // 根据要找的排名与两条分界线的位置，去不同的区间递归查找第 k 大的数 // 如果小于 pivot 的元素个数比k多，则第 k 大的元素一定是一个小于 pivot 的元素 if (rk < j) return find_kth_element(arr, rk, j); // 否则，如果小于 pivot 和等于 pivot 的元素加起来也没有 k 多， // 则第 k 大的元素一定是一个大于 pivot 的元素 else if (rk >= k) return find_kth_element(arr + k, rk - k, len - k); // 否则，pivot 就是第 k 大的元素 return pivot; } 改进：中位数中的中位数中位数中的中位数（英文：Median of medians），提供了一种确定性的选择划分过程中分界值的方法，从而能够让找第 𝑘k 大的数算法在最坏情况下也能实现线性时间复杂度． 该算法的流程如下： 将整个序列划分为 ⌊𝑛5⌋⌊n5⌋ 组，每组元素数不超过 5 个；寻找每组元素的中位数（因为元素个数较少，可以直接使用 插入排序 等算法）．找出这 ⌊𝑛5⌋⌊n5⌋ 组元素中位数中的中位数．将该元素作为前述算法中每次划分时的分界值即可．时间复杂度证明下面将证明，该算法在最坏情况下的时间复杂度为 𝑂(𝑛)O(n)．设 𝑇(𝑛)T(n) 为问题规模为 𝑛n 时，解决问题需要的计算量． 先分析前两步——划分与寻找中位数．由于划分后每组内的元素数量非常少，可以认为寻找一组元素的中位数的时间复杂度为 𝑂(1)O(1)．因此找出所有 ⌊𝑛5⌋⌊n5⌋ 组元素中位数的时间复杂度为 𝑂(𝑛)O(n)． 接下来分析第三步——递归过程．这一步进行了两次递归调用：第一次是寻找各组中位数中的中位数，需要的开销显然为 𝑇(𝑛5)T(n5)，第二次是进入分界值的左侧部分或右侧部分．根据我们选取的划分元素，有 12 ×⌊𝑛5⌋ =⌊𝑛10⌋12×⌊n5⌋=⌊n10⌋ 组元素的中位数小于分界值，这几组元素中，比中位数还小的元素也一定比分界值要小，从而整个序列中小于分界值的元素至少有 3 ×⌊𝑛10⌋ =⌊3𝑛10⌋3×⌊n10⌋=⌊3n10⌋ 个．同理，整个序列中大于分界值的元素也至少有 ⌊3𝑛10⌋⌊3n10⌋ 个．因此，分界值的左边或右边至多有 7𝑛107n10 个元素，这次递归的时间开销的上界为 𝑇(7𝑛10)T(7n10)． 综上，我们可以列出这样的不等式： 𝑇(𝑛)≤𝑇(𝑛5)+𝑇(7𝑛10)+𝑂(𝑛)T(n)≤T(n5)+T(7n10)+O(n)假设 𝑇(𝑛) =𝑂(𝑛)T(n)=O(n) 在问题规模足够小时成立．根据定义，此时有 𝑇(𝑛) ≤𝑐𝑛T(n)≤cn，其中 𝑐c 为一正常数．将不等式右边的所有 𝑇(𝑛)T(n) 进行代换： 𝑇(𝑛)≤𝑇(𝑛5)+𝑇(7𝑛10)+𝑂(𝑛)≤𝑐𝑛5+7𝑐𝑛10+𝑂(𝑛)≤9𝑐𝑛10+𝑂(𝑛)=𝑂(𝑛)T(n)≤T(n5)+T(7n10)+O(n)≤cn5+7cn10+O(n)≤9cn10+O(n)=O(n)到这里我们就证明了，该算法在最坏情况下也具有 𝑂(𝑛)O(n) 的时间复杂度． 参考资料与注释C++ 性能榨汁机之局部性原理 - I'm Root lee ! ↩ 三种快速排序以及快速排序的优化 ↩ introsort ↩ 算法实现/排序/快速排序 - 维基教科书，自由的教学读本 ↩↩↩ 本页面最近更新：2026/1/7 08:56:54，更新历史发现错误？想一起完善？ 在 GitHub 上编辑此页！本页面贡献者：NachtgeistW, Enter-tainer, Xeonacid, billchenchina, ksyx, iamtwz, ouuan, StudyingFather, Tiphereth-A, Alisahhh, Backl1ght, ChungZH, Ir1d, Konano, mcendu, Menci, partychicken, PhantomPower82, sbofgayschool, shawlleyw, sshwy, untitledunrevised, weilycoder, wpcwzy, xzcxzcyy, zhangjunyan2580, ZnPdCo本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用