快速排序：核心知识点全解析

一、快速排序 核心所有知识点1. 核心思想分治 挖坑 / 左右双指针 基准值 pivot选一个基准值pivot把数组划分成左边 ≤ pivot右边 ≥ pivot递归对左、右子区间重复划分区间长度为 1 时终止整体有序2. 时间复杂度平均\(O(n\log n)\)最坏\(O(n^2)\)已有序 / 逆序pivot 选最左 / 最右空间复杂度\(O(\log n)\)递归栈最坏 \(O(n)\)3. 稳定性不稳定排序相同元素相对位置会被打乱。4. 基准值 pivot 选法固定选最左 / 最右简单有序数组会退化三数取中左、中、右选中间值避免最坏情况随机选 pivot概率上很难退化5. 划分方式左右双指针交换法最常用挖坑法前后指针法适合链表6. 优化手段面试常问三数取中选 pivot规避有序数组退化小区间改用插入排序递归深度小、常数更小尾递归优化减少递归栈深度三路快排把数组分成小于、等于、大于三段处理重复值超多的数组复杂度降到 \(O(n)\)7. 特性总结原地排序不需要额外数组空间不稳定平均效率极高实际工程默认首选排序重复值多容易退化需三路快排优化二、基础版快排左右指针法 源代码cpp#include iostream #include vector using namespace std; // 划分返回基准值最终位置 int partition(vectorint arr, int left, int right) { int pivot arr[left]; // 选最左为基准 int l left, r right; while (l r) { // 从右找 pivot while (l r arr[r] pivot) r--; // 从左找 pivot while (l r arr[l] pivot) l; swap(arr[l], arr[r]); } // 基准归位 swap(arr[left], arr[l]); return l; } // 快速排序递归 void quickSort(vectorint arr, int left, int right) { if (left right) return; int pos partition(arr, left, right); quickSort(arr, left, pos - 1); quickSort(arr, pos 1, right); } int main() { vectorint arr {5,2,9,3,7,6,1,8,4}; quickSort(arr, 0, arr.size()-1); for (int x : arr) cout x ; return 0; }三、优化 1三数取中 选 pivotcpp// 三数取中 int midOfThree(vectorint arr, int l, int r) { int mid l (r - l) / 2; if(arr[l] arr[mid]) swap(arr[l], arr[mid]); if(arr[l] arr[r]) swap(arr[l], arr[r]); if(arr[mid] arr[r]) swap(arr[mid], arr[r]); // 把中间值放到 left 位置当 pivot swap(arr[mid], arr[l]); return arr[l]; } int partitionMid(vectorint arr, int left, int right) { int pivot midOfThree(arr, left, right); int l left, r right; while (l r) { while (l r arr[r] pivot) r--; while (l r arr[l] pivot) l; swap(arr[l], arr[r]); } swap(arr[left], arr[l]); return l; }四、优化 2三路快排处理大量重复值把数组分成 pivot| pivot| pivot重复区间不用再递归效率极高。cppvoid quickSort3Way(vectorint arr, int l, int r) { if (l r) return; int pivot arr[l]; int lt l, i l1, gt r; while (i gt) { if (arr[i] pivot) swap(arr[lt], arr[i]); else if (arr[i] pivot) swap(arr[i], arr[gt--]); else i; } // 只递归小于和大于区间 quickSort3Way(arr, l, lt-1); quickSort3Way(arr, gt1, r); }