引言前面我们学习了冒泡、选择、插入、基数四种排序。今天要讲的快速排序是二十世纪十大算法之一也是实际工程中最常用的排序算法。C 语言的qsort、C 的std::sort、Java 的Arrays.sort底层都是快速排序或其变体。快速排序的核心是分治思想选一个基准值把数组分成比基准小和比基准大两半然后递归处理两半。这种大事化小的策略让它的平均时间复杂度达到了 O(n log n)而且常数因子比归并排序和堆排序都小。第一部分算法思想一、核心原理快速排序的三步选基准从数组中选一个元素作为基准值pivot划分把小于基准的放左边大于基准的放右边递归对左右两部分分别重复这个过程二、挖坑法划分过程挖坑法口诀左边挖坑右边填右边挖坑左边填左右相遇放基准。第二部分代码实现一、挖坑法划分函数int Partition(int arr[], int left, int right) { int tmp arr[left]; // 基准值左边留下第一个坑 while (left ! right) { // 从右向左找比基准小的填左坑 while (left right arr[right] tmp) { right--; } if (left right) break; arr[left] arr[right]; // 小的放左边右边留下坑 // 从左向右找比基准大的填右坑 while (left right arr[left] tmp) { left; } if (left right) break; arr[right] arr[left]; // 大的放右边左边留下坑 } arr[left] tmp; // 基准值归位 return left; // 返回基准位置 }二、递归版本void Quick_Recursion(int arr[], int left, int right) { // 区间不合法或只有一个元素 → 终止 if (left right) return; // 划分得到基准位置 int par Partition(arr, left, right); // 递归处理左右两部分 Quick_Recursion(arr, left, par - 1); Quick_Recursion(arr, par 1, right); } void Quick_Sort(int arr[], int len) { Quick_Recursion(arr, 0, len - 1); }三、非递归版本用栈模拟递归#include stack void Quick_Sort_No_Recursion(int arr[], int len) { std::stackint s; s.push(0); // 先压左边界 s.push(len - 1); // 再压右边界 while (!s.empty()) { int right s.top(); s.pop(); // 先取右边界 int left s.top(); s.pop(); // 再取左边界 int par Partition(arr, left, right); // 左半部分还有多个元素 → 压栈 if (left par - 1) { s.push(left); s.push(par - 1); } // 右半部分还有多个元素 → 压栈 if (right par 1) { s.push(par 1); s.push(right); } } }递归 vs 非递归版本优点缺点递归代码简洁深度过大可能栈溢出非递归栈在堆上不易溢出代码稍长第三部分完整测试代码#include stdio.h #include stack int Partition(int arr[], int left, int right) { int tmp arr[left]; while (left ! right) { while (left right arr[right] tmp) right--; if (left right) break; arr[left] arr[right]; while (left right arr[left] tmp) left; if (left right) break; arr[right] arr[left]; } arr[left] tmp; return left; } void Quick_Recursion(int arr[], int left, int right) { if (left right) return; int par Partition(arr, left, right); Quick_Recursion(arr, left, par - 1); Quick_Recursion(arr, par 1, right); } void Quick_Sort(int arr[], int len) { Quick_Recursion(arr, 0, len - 1); } void printArray(int arr[], int len, const char* msg) { printf(%s, msg); for (int i 0; i len; i) printf(%d , arr[i]); printf(\n); } int main() { int arr1[] {5, 3, 8, 1, 2, 7, 6, 4}; int len1 sizeof(arr1) / sizeof(arr1[0]); printArray(arr1, len1, 排序前); Quick_Sort(arr1, len1); printArray(arr1, len1, 排序后); int arr2[] {1, 2, 3, 4, 5, 6, 7, 8}; int len2 sizeof(arr2) / sizeof(arr2[0]); printf(\n已有序测试\n); printArray(arr2, len2, 排序前); Quick_Sort(arr2, len2); printArray(arr2, len2, 排序后); int arr3[] {8, 7, 6, 5, 4, 3, 2, 1}; int len3 sizeof(arr3) / sizeof(arr3[0]); printf(\n逆序测试\n); printArray(arr3, len3, 排序前); Quick_Sort(arr3, len3); printArray(arr3, len3, 排序后); return 0; }第四部分算法分析一、时间复杂度情况时间复杂度条件最好O(n log n)每次划分均匀基准恰好是中位数最坏O(n²)每次基准是最大/最小值如已有序数组取左端为基准平均O(n log n)随机数据最坏情况演示二、空间复杂度版本空间说明递归O(log n)递归栈深度非递归O(log n)显式栈三、稳定性快速排序是不稳定的。因为划分时的跳跃式填坑会破坏相等元素的相对顺序。第五部分优化策略一、三数取中法避免最坏情况// 取 left、mid、right 三者的中间值作为基准 int GetMidIndex(int arr[], int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[mid]) { if (arr[mid] arr[right]) return mid; else if (arr[left] arr[right]) return right; else return left; } else { if (arr[left] arr[right]) return left; else if (arr[mid] arr[right]) return right; else return mid; } } int Partition_Optimized(int arr[], int left, int right) { // 三数取中交换到 left 位置 int mid GetMidIndex(arr, left, right); int tmp arr[left]; arr[left] arr[mid]; arr[mid] tmp; // 后面和普通 Partition 一样 tmp arr[left]; while (left ! right) { while (left right arr[right] tmp) right--; if (left right) break; arr[left] arr[right]; while (left right arr[left] tmp) left; if (left right) break; arr[right] arr[left]; } arr[left] tmp; return left; }二、小数据量切换插入排序当区间小于一定阈值如 16时插入排序比快速排序更快void Quick_Recursion_Optimized(int arr[], int left, int right) { if (left right) return; // 小数据量直接用插入排序 if (right - left 1 16) { // 插入排序... return; } int par Partition_Optimized(arr, left, right); Quick_Recursion_Optimized(arr, left, par - 1); Quick_Recursion_Optimized(arr, par 1, right); }第六部分与各排序算法对比排序算法平均最坏空间稳定冒泡排序O(n²)O(n²)O(1)✅选择排序O(n²)O(n²)O(1)❌插入排序O(n²)O(n²)O(1)✅基数排序O(d×n)O(d×n)O(nr)✅快速排序O(n log n)O(n²)O(log n)❌希尔排序O(n^1.3)O(n²)O(1)❌归并排序O(n log n)O(n log n)O(n)✅堆排序O(n log n)O(n log n)O(1)❌总结一、核心要点要点内容算法思想分治选基准 → 划分 → 递归时间复杂度最好/平均 O(n log n)最坏 O(n²)空间复杂度O(log n)递归栈稳定性❌ 不稳定核心优化三数取中避最坏小数据切插入二、代码框架记忆三、一句话记忆快速排序选基准小的放左大的放右递归处理两边。平均 O(n log n) 且常数因子最小是最快的通用排序算法。但最坏会退化到 O(n²)需要用三数取中优化。