快速排序(简称“快排”)是一种基于分治思想实现的排序算法,它具有排序效率高、消耗资源少、容易实现等优点,是很多实际场景的首选排序算法。
快速排序算法的基本原理
对于给定的待排序序列,快速排序算法完成升序或降序排序的过程是:
从待排序序列中挑选出一个元素(假设为 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