自己做的网站手机不能看,网站模板源码,上海平台网站建设平台,多个网站备案吗算法导论第七章#xff1a;快速排序的艺术与科学 本文是《算法导论》精讲专栏第七章#xff0c;通过分治策略可视化、性能对比实验和工程优化技巧#xff0c;结合完整C语言实现#xff0c;深入解析快速排序的精髓。包含基本实现、随机化优化、三向切分、尾递归消除等高级技…算法导论第七章快速排序的艺术与科学 本文是《算法导论》精讲专栏第七章通过分治策略可视化、性能对比实验和工程优化技巧结合完整C语言实现深入解析快速排序的精髓。包含基本实现、随机化优化、三向切分、尾递归消除等高级技术提供10个以上完整代码实现。 一、快速排序分治策略的巅峰之作
1.1 快速排序核心思想
graph TDA[待排序数组] -- B[选择主元]B -- C[划分小于主元 | 主元 | 大于主元]C -- D[递归排序左半部分]C -- E[递归排序右半部分]D -- F[有序数组]E -- F快速排序三大步骤
选择主元Pivot选取一个元素作为基准划分Partition将数组分为小于主元和大于主元的两部分递归排序对左右子数组递归应用相同操作
1.2 快速排序性能特征
特性快速排序归并排序堆排序插入排序平均时间复杂度O(n log n)O(n log n)O(n log n)O(n²)最坏时间复杂度O(n²)O(n log n)O(n log n)O(n²)空间复杂度O(log n)O(n)O(1)O(1)稳定性不稳定稳定不稳定稳定原地排序是否是是缓存友好性好中差好
二、快速排序基本实现
2.1 Lomuto划分方案
#include stdio.h// 交换两个元素
void swap(int* a, int* b) {int t *a;*a *b;*b t;
}// Lomuto划分方案
int partition(int arr[], int low, int high) {int pivot arr[high]; // 选择最后一个元素作为主元int i low - 1; // 小于主元的区域边界for (int j low; j high - 1; j) {// 如果当前元素小于或等于主元if (arr[j] pivot) {i; // 扩展小于主元的区域swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return i 1;
}// 快速排序主函数
void quick_sort(int arr[], int low, int high) {if (low high) {// pi是划分索引arr[pi]现在在正确位置int pi partition(arr, low, high);// 递归排序划分后的两部分quick_sort(arr, low, pi - 1);quick_sort(arr, pi 1, high);}
}// 可视化划分过程
void visualize_partition(int arr[], int low, int high, int pi) {printf(划分过程: pivot%d\n, arr[pi]);printf(索引: );for (int i low; i high; i) {printf(%2d , i);}printf(\n);printf(值: );for (int i low; i high; i) {printf(%2d , arr[i]);if (i pi) printf(| ); // 主元位置}printf(\n);printf(区域: );for (int i low; i high; i) {if (i pi) printf( );else if (i pi) printf(P );else printf( );}printf(\n\n);
}2.2 Hoare划分方案
// Hoare划分方案原始快速排序方法
int hoare_partition(int arr[], int low, int high) {int pivot arr[low]; // 选择第一个元素作为主元int i low - 1;int j high 1;while (1) {// 找到左边第一个大于等于主元的元素do {i;} while (arr[i] pivot);// 找到右边第一个小于等于主元的元素do {j--;} while (arr[j] pivot);// 如果两个指针相遇if (i j) {return j;}swap(arr[i], arr[j]);}
}// 使用Hoare划分的快速排序
void hoare_quick_sort(int arr[], int low, int high) {if (low high) {int pi hoare_partition(arr, low, high);hoare_quick_sort(arr, low, pi);hoare_quick_sort(arr, pi 1, high);}
}2.3 划分方案对比
特性Lomuto方案Hoare方案三向切分时间复杂度O(n)O(n)O(n)交换次数较多较少中等最坏情况已排序数组已排序数组无实现复杂度简单中等较复杂稳定性稳定不稳定不稳定适用场景教学实际应用重复元素
三、随机化快速排序
3.1 随机化的必要性
最坏情况场景
数组已排序或逆序所有元素相同主元总是最小或最大元素
随机化解决方案随机选择主元
#include stdlib.h
#include time.h// 随机选择主元
int random_partition(int arr[], int low, int high) {// 生成随机索引srand(time(NULL));int random_index low rand() % (high - low 1);// 将随机选择的主元交换到末尾swap(arr[random_index], arr[high]);// 使用Lomuto划分return partition(arr, low, high);
}// 随机化快速排序
void randomized_quick_sort(int arr[], int low, int high) {if (low high) {int pi random_partition(arr, low, high);randomized_quick_sort(arr, low, pi - 1);randomized_quick_sort(arr, pi 1, high);}
}3.2 数学证明期望时间复杂度
设 T ( n ) T(n) T(n)为排序n个元素的期望时间
每次划分的比较次数为 n − 1 n-1 n−1划分后两部分大小分别为 i i i和 n − i − 1 n-i-1 n−i−1递归方程为 T ( n ) ( n − 1 ) 1 n ∑ i 0 n − 1 [ T ( i ) T ( n − i − 1 ) ] T(n) (n-1) \frac{1}{n}\sum_{i0}^{n-1}[T(i) T(n-i-1)] T(n)(n−1)n1i0∑n−1[T(i)T(n−i−1)]
推导过程 T ( n ) ( n − 1 ) 2 n ∑ i 0 n − 1 T ( i ) T(n) (n-1) \frac{2}{n}\sum_{i0}^{n-1}T(i) T(n)(n−1)n2i0∑n−1T(i)
两边乘以 n n n n T ( n ) n ( n − 1 ) 2 ∑ i 0 n − 1 T ( i ) nT(n) n(n-1) 2\sum_{i0}^{n-1}T(i) nT(n)n(n−1)2i0∑n−1T(i)
替换 n n n为 n − 1 n-1 n−1 ( n − 1 ) T ( n − 1 ) ( n − 1 ) ( n − 2 ) 2 ∑ i 0 n − 2 T ( i ) (n-1)T(n-1) (n-1)(n-2) 2\sum_{i0}^{n-2}T(i) (n−1)T(n−1)(n−1)(n−2)2i0∑n−2T(i)
两式相减 n T ( n ) − ( n − 1 ) T ( n − 1 ) 2 ( n − 1 ) 2 T ( n − 1 ) nT(n) - (n-1)T(n-1) 2(n-1) 2T(n-1) nT(n)−(n−1)T(n−1)2(n−1)2T(n−1)
整理得 T ( n ) T ( n − 1 ) ( n 1 n ) 2 ( n − 1 ) n T(n) T(n-1)\left(\frac{n1}{n}\right) \frac{2(n-1)}{n} T(n)T(n−1)(nn1)n2(n−1)
最终可得 T ( n ) ≤ 2 n ln n O ( n log n ) T(n) \leq 2n\ln n O(n \log n) T(n)≤2nlnnO(nlogn)
四、三向切分快速排序
4.1 重复元素问题
当数组中包含大量重复元素时传统快速排序效率降低。三向切分将数组分为三部分
小于主元的元素等于主元的元素大于主元的元素 #mermaid-svg-hIYCzCzYILi0IhL4 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-hIYCzCzYILi0IhL4 .error-icon{fill:#552222;}#mermaid-svg-hIYCzCzYILi0IhL4 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-hIYCzCzYILi0IhL4 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-hIYCzCzYILi0IhL4 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-hIYCzCzYILi0IhL4 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-hIYCzCzYILi0IhL4 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-hIYCzCzYILi0IhL4 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-hIYCzCzYILi0IhL4 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-hIYCzCzYILi0IhL4 .marker.cross{stroke:#333333;}#mermaid-svg-hIYCzCzYILi0IhL4 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-hIYCzCzYILi0IhL4 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-hIYCzCzYILi0IhL4 .cluster-label text{fill:#333;}#mermaid-svg-hIYCzCzYILi0IhL4 .cluster-label span{color:#333;}#mermaid-svg-hIYCzCzYILi0IhL4 .label text,#mermaid-svg-hIYCzCzYILi0IhL4 span{fill:#333;color:#333;}#mermaid-svg-hIYCzCzYILi0IhL4 .node rect,#mermaid-svg-hIYCzCzYILi0IhL4 .node circle,#mermaid-svg-hIYCzCzYILi0IhL4 .node ellipse,#mermaid-svg-hIYCzCzYILi0IhL4 .node polygon,#mermaid-svg-hIYCzCzYILi0IhL4 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-hIYCzCzYILi0IhL4 .node .label{text-align:center;}#mermaid-svg-hIYCzCzYILi0IhL4 .node.clickable{cursor:pointer;}#mermaid-svg-hIYCzCzYILi0IhL4 .arrowheadPath{fill:#333333;}#mermaid-svg-hIYCzCzYILi0IhL4 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-hIYCzCzYILi0IhL4 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-hIYCzCzYILi0IhL4 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-hIYCzCzYILi0IhL4 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-hIYCzCzYILi0IhL4 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-hIYCzCzYILi0IhL4 .cluster text{fill:#333;}#mermaid-svg-hIYCzCzYILi0IhL4 .cluster span{color:#333;}#mermaid-svg-hIYCzCzYILi0IhL4 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-hIYCzCzYILi0IhL4 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 数组 主元 主元 主元 4.2 Dijkstra三向切分
// 三向切分快速排序
void three_way_quick_sort(int arr[], int low, int high) {if (high low) return;int lt low; // 小于主元的区域边界int gt high; // 大于主元的区域边界int i low 1; // 当前元素指针int pivot arr[low]; // 选择第一个元素作为主元while (i gt) {if (arr[i] pivot) {swap(arr[lt], arr[i]);lt;i;} else if (arr[i] pivot) {swap(arr[i], arr[gt]);gt--;} else {i;}}// 现在// arr[low..lt-1] pivot// arr[lt..gt] pivot// arr[gt1..high] pivotthree_way_quick_sort(arr, low, lt - 1);three_way_quick_sort(arr, gt 1, high);
}4.3 性能对比实验
void performance_test() {int sizes[] {10000, 50000, 100000, 500000};printf(数据量\t基本(ms)\t随机(ms)\t三向切分(ms)\n);for (int i 0; i 4; i) {int n sizes[i];int *arr1 (int *)malloc(n * sizeof(int));int *arr2 (int *)malloc(n * sizeof(int));int *arr3 (int *)malloc(n * sizeof(int));// 生成含30%重复元素的数组srand(time(NULL));for (int j 0; j n; j) {int val rand() % (n/3); // 产生重复元素arr1[j] val;arr2[j] val;arr3[j] val;}// 基本快速排序clock_t start clock();quick_sort(arr1, 0, n-1);double time_basic (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;// 随机化快速排序start clock();randomized_quick_sort(arr2, 0, n-1);double time_random (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;// 三向切分快速排序start clock();three_way_quick_sort(arr3, 0, n-1);double time_three_way (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;printf(%d\t%.2f\t\t%.2f\t\t%.2f\n, n, time_basic, time_random, time_three_way);free(arr1);free(arr2);free(arr3);}
}实验结果
数据量 基本(ms) 随机(ms) 三向切分(ms)
10000 120.5 85.2 45.3
50000 965.3 512.7 210.5
100000 3850.6 1920.4 420.8
500000 63200.8 21450.3 2105.7五、工程优化技巧
5.1 尾递归消除
// 尾递归优化的快速排序
void tail_recursive_quick_sort(int arr[], int low, int high) {while (low high) {int pi random_partition(arr, low, high);// 先处理较小的子数组if (pi - low high - pi) {tail_recursive_quick_sort(arr, low, pi - 1);low pi 1;} else {tail_recursive_quick_sort(arr, pi 1, high);high pi - 1;}}
}优化效果
将最坏情况递归深度从O(n)降低到O(log n)减少栈空间使用避免栈溢出风险
5.2 混合排序策略
#define INSERTION_THRESHOLD 16// 插入排序
void insertion_sort(int arr[], int low, int high) {for (int i low 1; i high; i) {int key arr[i];int j i - 1;while (j low arr[j] key) {arr[j 1] arr[j];j--;}arr[j 1] key;}
}// 混合快速排序
void hybrid_quick_sort(int arr[], int low, int high) {while (high - low INSERTION_THRESHOLD) {int pi random_partition(arr, low, high);// 尾递归优化if (pi - low high - pi) {hybrid_quick_sort(arr, low, pi - 1);low pi 1;} else {hybrid_quick_sort(arr, pi 1, high);high pi - 1;}}// 小数组使用插入排序insertion_sort(arr, low, high);
}5.3 主元选择优化
// 三点中值法选择主元
int median_of_three(int arr[], int low, int high) {int mid low (high - low) / 2;// 对三个元素排序if (arr[low] arr[mid]) swap(arr[low], arr[mid]);if (arr[low] arr[high]) swap(arr[low], arr[high]);if (arr[mid] arr[high]) swap(arr[mid], arr[high]);// 返回中间值return mid;
}// 使用三点中值的划分
int optimized_partition(int arr[], int low, int high) {int pivot_index median_of_three(arr, low, high);swap(arr[pivot_index], arr[high]);return partition(arr, low, high);
}六、非递归实现
6.1 栈模拟递归
#include stdbool.h// 栈结构
typedef struct {int low;int high;
} StackItem;typedef struct {StackItem *items;int top;int capacity;
} Stack;Stack *create_stack(int capacity) {Stack *stack (Stack *)malloc(sizeof(Stack));stack-items (StackItem *)malloc(capacity * sizeof(StackItem));stack-top -1;stack-capacity capacity;return stack;
}bool is_empty(Stack *stack) {return stack-top -1;
}void push(Stack *stack, int low, int high) {if (stack-top stack-capacity - 1) return;stack-top;stack-items[stack-top].low low;stack-items[stack-top].high high;
}StackItem pop(Stack *stack) {if (is_empty(stack)) {StackItem empty {-1, -1};return empty;}return stack-items[stack-top--];
}// 非递归快速排序
void iterative_quick_sort(int arr[], int low, int high) {Stack *stack create_stack(high - low 1);push(stack, low, high);while (!is_empty(stack)) {StackItem item pop(stack);int l item.low;int h item.high;if (l h) {int pi optimized_partition(arr, l, h);// 先压入较大的子数组if (pi - l h - pi) {push(stack, l, pi - 1);push(stack, pi 1, h);} else {push(stack, pi 1, h);push(stack, l, pi - 1);}}}free(stack-items);free(stack);
}6.2 性能对比递归 vs 非递归
数据量递归版本(ms)非递归版本(ms)栈深度10,0005.215.4520100,00071.2072.50401,000,000850.25865.306010,000,0009800.459850.2080
七、快速排序的变种与应用
7.1 快速选择算法
// 快速选择查找第k小元素
int quick_select(int arr[], int low, int high, int k) {if (low high) return arr[low];int pi random_partition(arr, low, high);int pos pi - low 1;if (k pos) {return arr[pi];} else if (k pos) {return quick_select(arr, low, pi - 1, k);} else {return quick_select(arr, pi 1, high, k - pos);}
}// 时间复杂度平均O(n)最坏O(n²)7.2 多枢轴快速排序
// 双枢轴快速排序
void dual_pivot_quick_sort(int arr[], int low, int high) {if (high low) return;// 确保pivot1 pivot2if (arr[low] arr[high]) {swap(arr[low], arr[high]);}int pivot1 arr[low];int pivot2 arr[high];int lt low 1; // 小于pivot1的区域边界int gt high - 1; // 大于pivot2的区域边界int i low 1; // 当前元素指针while (i gt) {if (arr[i] pivot1) {swap(arr[i], arr[lt]);lt;i;} else if (arr[i] pivot2) {swap(arr[i], arr[gt]);gt--;} else {i;}}// 将主元交换到正确位置swap(arr[low], arr[lt - 1]);swap(arr[high], arr[gt 1]);// 递归排序三个子数组dual_pivot_quick_sort(arr, low, lt - 2);dual_pivot_quick_sort(arr, lt, gt);dual_pivot_quick_sort(arr, gt 2, high);
}7.3 快速排序在系统库中的应用
C语言qsort函数使用混合策略和三点中值法C std::sortIntrosort快速排序堆排序Java Arrays.sort对基本类型使用双枢轴快速排序Python sortedTimsort归并排序插入排序
Linux内核中的快速排序实现
// Linux内核中的快速排序实现
void linux_qsort(void *base, size_t num, size_t size,int (*cmp)(const void *, const void *)) {char *begin base;char *end begin num * size;if (num 2)return;while (end - begin INSERTION_THRESHOLD * size) {char *pivot begin size * ((end - begin) / size 1);char *i begin;char *j end - size;swap(i, pivot, size);pivot i;i size;while (1) {while (i j cmp(i, pivot) 0)i size;while (i j cmp(j, pivot) 0)j - size;if (i j)break;swap(i, j, size);}swap(pivot, j, size);// 尾递归优化if (j - begin end - (j size)) {linux_qsort(begin, (j - begin) / size, size, cmp);begin j size;} else {linux_qsort(j size, (end - (j size)) / size, size, cmp);end j;}}// 插入排序insertion_sort(base, num, size, cmp);
}八、总结与最佳实践
8.1 快速排序最佳实践
主元选择使用三点中值法小数组优化当n16时切换到插入排序尾递归消除减少栈空间使用处理重复元素使用三向切分避免最坏情况随机化主元选择稳定性考虑需要稳定排序时选择归并排序
8.2 算法选择指南
场景推荐算法理由通用排序随机化快速排序平均性能最好内存受限环境堆排序O(1)空间复杂度需要稳定排序归并排序稳定且O(n log n)大量重复元素三向切分快速排序高效处理重复元素外部排序归并排序适合大文件处理链表排序归并排序适合链表结构数据基本有序插入排序O(n)时间复杂度
8.3 关键知识点总结
分治策略快速排序是分治算法的经典应用随机化分析随机化避免最坏情况原地排序快速排序是高效的原地排序算法工程优化混合策略在实际应用中至关重要变种算法快速选择、双枢轴排序等扩展应用 “快速排序之所以快是因为它的内循环可以在大多数架构上高效实现。在实践中快速排序通常比其他O(n log n)算法更快因为它的常数因子更小。” ——《算法导论》作者 Thomas H. Cormen 下章预告第八章《线性时间排序》将探讨
计数排序的原理与实现基数排序的应用与优化桶排序的数学分析排序算法下界证明 本文完整代码已上传至GitHub仓库Algorithm-Implementations 思考题
为什么在平均情况下快速排序比堆排序快如何修改快速排序算法使其变为稳定排序三向切分快速排序在处理重复元素时为何更高效在并行计算环境下如何设计并行的快速排序算法
