八大排序算法 - 快速排序

一、算法介绍快速排序是分治思想经典排序实际应用效率极高属于不稳定排序。基本思想选一个基准值把数组分成左小右大两部分再递归排序左右区间。平均时间复杂度(O(nlog n))最坏时间复杂度(O(n^2))空间复杂度(O(log n))稳定性不稳定二、核心流程选取基准数常用最左、最右、中间值左右指针遍历小值放左边大值放右边基准归位划分左右两个子区间递归对左右区间重复操作完成排序三、代码#include iostream #include vector using namespace std; // 快排核心 void quickSort(vectorint arr, int l, int r) { if(l r) return; int i l, j r; int pivot arr[l]; // 选最左为基准 while(i j) { while(ij arr[j]pivot) j--; arr[i] arr[j]; while(ij arr[i]pivot) i; arr[j] arr[i]; } arr[i] pivot; quickSort(arr,l,i-1); quickSort(arr,i1,r); } void print(vectorint a) { for(int x:a) coutx ; coutendl; } int main() { vectorint nums{6,2,7,1,9,3,8,5}; cout排序前;print(nums); quickSort(nums,0,nums.size()-1); cout排序后;print(nums); return 0; }四、优缺点优点平均速度最快日常排序首选原地排序内存开销小大数据量排序性能极强缺点极端情况效率退化到\(O(n^2)\)不稳定相等元素顺序会打乱递归太深容易栈溢出五、使用场景日常开发数组排序首选大数据量无序序列排序笔试面试最常手写排序算法