快速排序算法图文详解
- 作者: 洞洞我拭使
- 来源: 51数据库
- 2022-09-23
快速排序（简称“快排”）是一种基于分治思想实现的排序算法，它具有排序效率高、消耗资源少、容易实现等优点，是很多实际场景的首选排序算法。
快速排序算法的基本原理
对于给定的待排序序列，快速排序算法完成升序或降序排序的过程是：
从待排序序列中挑选出一个元素（假设为 pivot），将待排序序列中的剩余元素分为 2 个子序列，一个子序列中的所有元素都比 pivot 小，另一个子序列中的所有元素都比 pivot大；
除非子序列不存在或者不可再分（仅有 1 个元素），否则将 2 个子序列分别看做待排序序列，各自重复执行第 1 步。
如下为实现快速排序算法的伪代码：
输入 arr[] // 输入待排序序列
quick_sort(arr[] , p , q): // [p , q] 用于执行进行快速排序的区域
if q-p <= 0: // 如果待排序不存在或者序列中仅有 1 个元素，则直接返回
return
else:
par <- partition(arr , p , q) // 调用 partition() 函数分割 [p , q] 序列，使 [p , par-1] 区域的元素都比 pivot 小，[par+1 , q] 区域的元素都比 pivot 大
quick_sort(arr , p , par-1) // 将 [p , par-1] 作为待排序序列，重复进行分割
quick_sort(arr , par+1 , q) // 将 [par+1 , q] 作为待排序序列，重复进行分割
了解了快速排序的实现过程之后，接下来讨论一个问题：如何实现将 [p , q] 区域分割成 [p , par-1] 和 [par+1 , q] 这两个子区域，保证 [p , par] 区域中的元素都比 par 位置上的元素 pivot 小，[par+1 , q] 区域内的元素都比 pivot 大。换句话说，如何实现伪代码中的 partition() 函数？
事实上，实现此功能的方法有很多种，这里以分割如下待排序序列为例，给您介绍一种方法。
1) 选择待排序序列中最后一个元素作为 pivot，同时建立 2 个指针分别指向第一个元素和倒数第 2 个元素，为遍历序列做准备，如下图所示：
2) lo 指针从指向的元素开始依次向右遍历，每个元素都同 31 做比较，直至找到一个不小于 31 的值，显然 35>31，如下图所示。
hi 指针从指向的元素开始依次向左遍历，每个元素都同 31 做比较，直至找到一个不大于 31 的值，显然 26<31，如下图所示：
3) 交换 lo 和 hi 指向的值，如下图所示：
4) 返回第 2 步继续执行，直至 lo ≥ hi。此时，交换 lo 和 pivot 的值。下面的动画演示了后续的整个过程：
再次强调，比较 lo 和 hi 使用的是 ≥ 运算符，因为当待排序序列本身为有序序列时（比如 {1,2,3,4,5,6,7}），执行第 2 步，lo 指针会一直遍历至指向最后一个元素 pivot，就会出现 lo＞hi 的情况。
如下为实现 partition() 函数的伪代码：
partition(arr[] , p , q): // [p , q] 为要分割的区域
lo <- p // lo、hi 准备遍历 [p , q-1] 区域
hi <- q-1
pivot <- arr[q] // 以 [p , q] 区域中最后一个元素作为中间值
while true： // 一直循环，直到执行 end while
while arr[lo] < pivot: // lo 从左往右遍历，直至找到一个不小于 pivot 的元素
lo <- lo+1
while hi>0 and arr[hi] > pivot: // hi 从右往左遍历，直至找到一个不小于 pivot 的元素
hi <- hi-1
if lo ≥ hi: // 如果 lo 大于等于 hi，退出循环
end while
else:
swap arr[lo] , arr[hi] // 交换 arr[lo] 和 arr[hi] 的值
lo <- lo+1 // 分别将 lo 和 hi 向前移动一步，准备遍历后续的元素
hi <- hi-1
swap arr[lo] , arr[q] // 跳出循环后，交换 arr[lo] 和 arr[q] 的值
return lo // 返回 lo 的值，也就是中间值所在序列中的位置
快速排序算法的具体实现
最坏情况下，快速排序算法的时间复杂度为O(n2)，该排序算法的平均时间复杂度为O(nlogn)。
如下为实现快速排序算法的 C 语言程序：
#include <stdio.h>
// arr 为待排序数组，[p,q] 用于指定排序区域
int partition(int *arr,int p, int q) {
int temp = 0;
// lo、hi分别表示指向首个元素和倒数第 2 个元素的指针
int lo = p;
int hi = q - 1;
//pivot 表示选中的中间值
int pivot = arr[q];
while (1)
{
//lo从左往右遍历，直至找到一个不小于 pivot 的元素
while (arr[lo] < pivot) {
lo++;
};
//hi从右往左遍历，直至找到一个不大于 pivot 的元素
while (hi > 0 && arr[hi] > pivot) {
hi--;
}
//如果 lo≥hi，退出循环
if (lo >= hi)
{
break;
}
else {
//交换 arr[lo] 和 arr[hi] 的值
temp = arr[lo];
arr[lo] = arr[hi];
arr[hi] = temp;
// lo 和 hi 都向前移动一个位置，准备继续遍历
lo++;
hi--;
}
}
//交换 arr[lo] 和 arr[q] 的值
temp = arr[lo];
arr[lo] = pivot;
arr[q] = temp;
//返回中间值所在序列中的位置
return lo;
}
void quick_sort(int* arr, int p, int q) {
int par;
//如果待排序序列不存在，或者仅包含 1 个元素，则不再进行分割
if (q - p <= 0) {
return;
}
else {
//调用 partition() 函数，分割 [p,q] 区域
par = partition(arr, p, q);
//以 [p,par-1]作为新的待排序序列，继续分割
quick_sort(arr, p, par - 1);
//以[par+1,q]作为新的待排序序列，继续分割
quick_sort(arr, par + 1, q);
}
}
int main()
{
int i = 0;
int arr[10] = { 35,33,42,10,14,19,27,44,26,31 };
//对于 arr 数组中所有元素进行快速排序
quick_sort(arr, 0, 9);
for (; i < 10; i++) {
printf("%d ", arr[i]);
}
return 0;
}
如下为实现快速排序算法的 Java 程序：
public class Demo {
public static int partition(int[] arr, int p, int q) {
int temp = 0;
// lo、hi分别表示指向首个元素和倒数第 2 个元素的指针
int lo = p;
int hi = q - 1;
// pivot 表示选中的中间值
int pivot = arr[q];
while (true) {
// lo从左往右遍历，直至找到一个不小于 pivot 的元素
while (arr[lo] < pivot) {
lo++;
}
// hi从右往左遍历，直至找到一个不大于 pivot 的元素
while (hi > 0 && arr[hi] > pivot) {
hi--;
}
// 如果 lo≥hi，退出循环
if (lo >= hi) {
break;
} else {
// 交换 arr[lo] 和 arr[hi] 的值
temp = arr[lo];
arr[lo] = arr[hi];
arr[hi] = temp;
// lo 和 hi 都向前移动一个位置，准备继续遍历
lo++;
hi--;
}
}
// 交换 arr[lo] 和 arr[q] 的值
temp = arr[lo];
arr[lo] = pivot;
arr[q] = temp;
// 返回中间值所在序列中的位置
return lo;
}
public static void quick_sort(int[] arr, int p, int q) {
//如果待排序序列不存在，或者仅包含 1 个元素，则不再进行分割
if (q - p <= 0) {
return;
} else {
//调用 partition() 函数，分割 [p,q] 区域
int par = partition(arr, p, q);
//以 [p,par-1]作为新的待排序序列，继续分割
quick_sort(arr, p, par - 1);
//以[par+1,q]作为新的待排序序列，继续分割
quick_sort(arr, par + 1, q);
}
}
public static void main(String[] args) {
int[] arr = new int[] { 35, 33, 42, 10, 14, 19, 27, 44, 26, 31 };
// 对于 arr 数组中所有元素进行快速排序
quick_sort(arr, 0, 9);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
如下为实现快速排序算法的 Python 程序：
格式化复制
def partition(arr,p,q): #lo、hi分别表示指向首个元素和倒数第 2 个元素的索引 lo = p hi = q-1 #pivot 表示选中的中间值 pivot = arr[q] while True: #lo从左往右遍历，直至找到一个不小于 pivot 的元素 while arr[lo] < pivot: lo = lo + 1 #hi从右往左遍历，直至找到一个不大于 pivot 的元素 while hi > 0 and arr[hi] > pivot: hi = hi - 1 #如果 lo≥hi，退出循环 if lo >= hi: break else: #交换 arr[lo] 和 arr[hi] 的值 arr[lo],arr[hi] = arr[hi],arr[lo] #lo 和 hi 都向前移动一个位置，准备继续遍历 lo = lo + 1 hi = hi - 1 #交换 arr[lo] 和 arr[q] 的值 arr[lo],arr[q] = arr[q],arr[lo] #返回中间值所在序列中的位置 return lo def quick_sort(arr,p,q): #如果待排序序列不存在，或者仅包含 1 个元素，则不再进行分割 if q - p <= 0: return #调用 partition() 函数，分割 [p,q] 区域 par = partition(arr,p,q) #以 [p,par-1]作为新的待排序序列，继续分割 quick_sort(arr,p,par-1) #以[par+1,q]作为新的待排序序列，继续分割 quick_sort(arr,par+1,q) arr=[35,33,42,10,14,19,27,44,26,31] #对于 arr 列表中所有元素进行快速排序 quick_sort(arr,0,9) print(arr)
以上程序的执行结果均为：
10 14 19 26 27 31 33 35 42 44
