引言想象一下当你打开手机通讯录寻找一个朋友时当你在电商网站按价格筛选商品时或者当搜索引擎在毫秒间为你呈现最相关的结果时——排序这个看似简单的操作正在悄无声息地支撑着现代数字生活的每一次高效交互。排序算法是计算机科学中最基础、最核心的领域之一其重要性远超表面所见。在众多排序算法中快速排序占据着独特的位置。自1960年由英国计算机科学家托尼·霍尔发明以来它以其优雅的“分而治之”策略和卓越的平均性能成为实际应用中最广泛使用的排序算法。从C语言的qsort()到Java的Arrays.sort()从Python的sorted()到浏览器JavaScript引擎快速排序的身影无处不在。这是排序专题的第一篇内容我们将以托尼·霍尔发明的快速排序作为开篇。一、快排原理整体逻辑快速排序用的是分而治之的思想以从小到大的顺序为例我们要做以下工作1、在整个区间中选取一个基准key。2、把基准放在它该在的位置上把比它小的数放左边比它大的数放右边。3、对这个基准左边的区间和右边的区间再分别进行快速排序。如上我们可以先写个大框架voidQuickSort(int*a,intn){if(有序了)return;intkey;//选一个基准_QuickSort();//假设这是单趟排序的逻辑QuickSort(左区间);QuickSort(右区间);}单趟逻辑在单趟排序中我们一般把基准值放在第一个这样方便代码实现之后我们定义一个left和一个right分别从两头遍历数组。right先走找到比key小的值就停下left再走找比key大的值两个都停下后交换left和right的值。一直重复此过程直到left和right相遇此时相遇位置的值比key小且相遇位置是key应该在的位置交换相遇位置与key的值此时key在它该在的位置上比它小的数都在它左边比它大的数都在它右边单趟排序完成。最后再对key的左右区间递归递归完成后排序结束。为什么相遇位置的值比key小相遇位置有两种情况1、left遇到right我们是让right先走如果是left遇到right说明是right先停下而right停下的条件是找到比key小的值left与right相遇后位置的值就是比key小的值。2、right遇到left上一趟left找到比key大的值之后与上一趟的right找到的比key小的值交换所以上一趟的left存的是比key小的值。而right遇到left说明right没有遇到比key小的值直接与上一趟的left相遇此时相遇位置也是比key小的值。二、代码实现voidSwap(int*x,int*y){inttmp*x;*x*y;*ytmp;}intpartion(inta[],intleft,intright){intkeya[left];intileft,jright;while(ij){while(ija[j]key)//右边找小j--;while(ija[i]key)//左边找大i;if(ij)Swap(a[i],a[j]);//找到交换若ij则意味着没有两个都找到就相遇了}Swap(a[left],a[i]);//交换相遇位置与key的值returni;}//快速排序voidQuickSort(inta[],intleft,intright){if(leftright)return;intmidpartion(a,left,right);//记录key的值//对左右区间递归QuickSort(a,left,mid-1);QuickSort(a,mid1,right);}三、快排优化根据上面的代码我们知道快排的Hoare法是用递归实现的那么如果递归深度太深就容易造成栈溢出。那么我们看这样一种场景假如对一堆正序的n个数据排序我们先选择第一个数为key此时第一个数已经在它的位置上了因为是正序的数据。然后我们划分左右区间递归左区间没有右区间是除了key的n-1个数。这时候再进行第二层排序左区间依旧没有右区间是除了key的n-2个数。以此推类我们需要n层栈帧才能完成这次排序效率极低。为了解决快排的一系列问题我们可以做出很多优化1. 随机选 key在排序区间内随机选取一个元素作为 key能有效避免数据分布带来的最坏情况但随机数生成本身有一定开销。intGetRandomKey(intleft,intright){srand(time(NULL));// 需确保只调用一次returnrand()%(right-left1)left;}intPartSort(int*a,intleft,intright){intkeyiGetRandomKey(left,right);Swap(a[keyi],a[left]);// 将 key 换到最左边保持原有分区逻辑// 后续分区逻辑不变 ...}2. 三数取中法最推荐取区间 [left, right] 的第一个元素、中间元素、最后一个元素比较三者大小选择值居中的元素作为 key。这种方法能有效避免极端情况且无需额外开销。intGetMidIndex(int*a,intleft,intright){intmid(leftright)/2;if(a[left]a[mid]){if(a[mid]a[right])returnmid;// left mid rightelseif(a[left]a[right])returnright;// left right midelsereturnleft;// right left mid}else{// a[left] a[mid]if(a[left]a[right])returnleft;// mid left rightelseif(a[mid]a[right])returnright;// mid right leftelsereturnmid;// right mid left}}intPartSort(int*a,intleft,intright){intmidiGetMidIndex(a,left,right);Swap(a[midi],a[left]);// 将中位数换到最左边// 后续分区逻辑不变 ...}取三个数: 3, 9, 8排序后: 3, 8, 9中间值: 8 ← 选作 key比 3 更接近中位数3. 小区间优化递归降级当子区间规模小于某个阈值时不再使用递归而是直接调用插入排序。插入排序在小数据量下常数小、效率高同时减少了递归深度。voidQuickSort(int*a,intleft,intright){// 小区间优化数据量小于 10 时改用插入排序if(right-left110){InsertSort(aleft,right-left1);return;}// 继续快排逻辑...}//阈值选择建议 一般取 10 20 之间//太大会浪费快排的优势太小则优化效果不明显。4.三路划分处理大量重复数据当数组中有大量重复元素时传统的左右分区方法会将所有等于 key 的元素集中在同一侧导致分区不均衡。三路划分将数组分为三部分[left, less] → 小于 key[less1, great-1] → 等于 key[great, right] →大于 keyvoidQuickSortThreeWay(int*a,intleft,intright){if(leftright)return;intkeya[left];intlessleft;intgreatright;intileft1;while(igreat){if(a[i]key){Swap(a[less],a[i]);less;i;}elseif(a[i]key){Swap(a[i],a[great]);great--;}else{i;}}// 递归处理小于 key 和大于 key 的部分QuickSortThreeWay(a,left,less-1);QuickSortThreeWay(a,great1,right);}适用场景 数组中大量重复值如成绩统计、性别分类等可大幅提升效率。四、非递归快排我们能否模拟压栈与出栈来实现一个不需要递归的快速排序呢当然可以具体做法是使用显式栈模拟递归过程将需要处理的区间压入栈中循环取出处理。voidQuickSortNonR(int*a,intleft,intright){Stack st;StackInit(st);StackPush(st,right);StackPush(st,left);// 先压左后压右取时先右后左while(!StackEmpty(st)){intbeginStackTop(st);StackPop(st);intendStackTop(st);StackPop(st);intkeyiPartSort(a,begin,end);// [begin, keyi-1] 和 [keyi1, end] 入栈if(keyi1end){StackPush(st,end);StackPush(st,keyi1);}if(beginkeyi-1){StackPush(st,keyi-1);StackPush(st,begin);}}StackDestroy(st);}