快排基础性质配套背诵平均时间\(O(nlogn)\)最坏时间\(O(n^2)\)有序 选端点做基准空间复杂度递归栈平均\(O(logn)\)最坏\(O(n)\)不稳定排序// 快速排序的一次划分int Partition (int* arr, int low, int high)//O (n),O (1){int tmp arr [low];// 基准while (low high){// 从后往前找比基准小的数字往前移动while (lowhigh arr [high] tmp){high--;}if (low high){arr [low] arr [high];}// 从前往后找比基准大的数据往后移动while (low high arr [low] tmp){low;}if (low high){arr [high] arr [low];}}arr [low] tmp;return low;}void Quick (int* arr,int low, int high){int par Partition (arr, low,high);if (low par - 1)// 左边的数据个数超过一个{Quick (arr, low, par - 1);}if (par 1 high){Quick (arr, par 1, high);}}// 快速排序void QuickSort (int* arr, int len)//(nlogn),O (logn), 不稳定 (缺点){Quick (arr, 0, len - 1);}快速排序的优化数据结构考试高频简答快排核心问题选到极差基准如最大 / 最小值退化为\(O(n^2)\)优化全部围绕基准、递归、小规模数组展开。1. 基准元素优化最常考① 三数取中法median-of-three取左端、右端、中间位置三个数选中间大小的值作为 pivot。避免在有序 / 逆序数组选到最值当基准大幅减少最坏情况概率。缺点多几次比较小规模数组收益不大。② 随机选基准随机在区间选一个元素作为 pivot。理论上避免有序数组退化适合数据分布未知场景。缺点随机数有开销考试里常和三数取中二选一。2. 小规模子数组改用直接插入排序当待排序区间长度很小一般阈值取 7~10不再递归快排直接插入排序。 原因 递归调用有栈开销小数组时直接插入常数更小比快排更快。3. 减少递归栈开销尾递归优化快排递归处理左右两段会产生递归栈。 优化思路优先递归短区间长区间改用循环处理。作用降低递归栈深度防止有序数据时栈溢出。最坏栈空间由\(O(n)\) → \(O(logn)\)void Quick(int* arr,int low, int high) { while(low high) // 长区间交给循环不压栈 { int par Partition(arr, low,high); // 左右区间选短的去递归长区间继续while if(par - low high - par) { Quick(arr, low, par - 1); // 短区间递归 low par 1; // 长区间留在循环 } else { Quick(arr, par 1, high); // 短区间递归 high par - 1; // 长区间留在循环 } } }4. 三路快排划分优化复试常考普通快排分成小于 pivot、大于 pivot 两段。 三路快排划分成三块小于 pivot、等于 pivot、大于 pivot✅ 适合大量重复元素的数组大量相等元素不再重复递归性能提升巨大。void Quick3way(int arr[], int low, int high) { if(low high) return; int pivot arr[low]; int lt low, gt high; int i low 1; while(i gt) { if(arr[i] pivot) { swap(arr[i], arr[lt]); lt; i; } else if(arr[i] pivot) { swap(arr[i], arr[gt]); gt--; } else // arr[i]pivot直接跳过 { i; } } // [low,lt-1]pivot , [lt,gt]pivot , [gt1,high]pivot Quick3way(arr, low, lt-1); Quick3way(arr, gt1, high); }5. 聚集相等元素另一种重复元素优化划分时把等于基准的元素放中间减少后续递归范围。
