java快速排序超详细总结：核心实现+简化版+趣味版

java快速排序超详细总结核心实现简化版趣味版面试高频 | 四种写法 | 含过程演示 | 新手友好概要详解快速排序三种写法挖坑法、双指针交换法、单指针法每种均附分步演示与代码注释。涵盖复杂度分析、稳定性及面试易错点附Python一行趣味版新手入门面试备战均适用。先说结论快速排序就干三件事选基准 → 分左右 → 递归重复。平均时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)原地排序实际运行效率很高是面试手撕排序的首选。一、核心思想用生活举例想象你在整理一堆扑克牌随手抽一张作为基准把比它小的全扔左边比它大的全扔右边 基准牌就稳稳坐在中间 然后对左边那堆、右边那堆重复同样的操作 直到每堆只剩一张牌整副牌就排好了这就是快排分治思想化大问题为小问题。二、挖坑法新手首选思路选左边第一个数当基准把它挖走留下一个坑。然后双指针从两端往中间夹找到合适的数就填坑自己变成新坑最后把基准填回指针相遇的位置。关键记忆点基准选左边必须先动右指针。过程演示动态演示静态演示再换一个数组以[5, 2, 9, 3, 8]为例基准 5首位初始[_, 2, 9, 3, 8] 坑在位置0pivot5 i j 第1步j从右往左找 ≤5 的数找到 arr[3]3 [3, 2, 9, _, 8] 把arr[3]3移到坑里面坑移到位置3 i j 第2步i从左往右找 ≥5 的数找到 arr[2]9 [3, 2, _, 9, 8] arr[2]9移到坑里面坑移到位置2 i j 第3步j继续往左找 ≤5 的数j移到位置2ij 相遇 回填基准:[3, 2, 5, 9, 8] ↑ 基准归位左边[3, 2]全 ≤ 5右边[9, 8]全 ≥ 5完美分区。完整代码publicclassQuickSort{publicstaticvoidmain(String[]args){int[]arr{5,2,9,3,8,4,1,7,6};quickSort(arr,0,arr.length-1);// 对整个数组排序System.out.println(Arrays.toString(arr));}privatestaticvoidquickSort(int[]arr,intleft,intright){if(leftright)return;// 区间只剩0或1个元素天然有序直接返回intpivotIndexpartition(arr,left,right);// 分区返回基准最终落的位置quickSort(arr,left,pivotIndex-1);// 递归处理基准左边的部分quickSort(arr,pivotIndex1,right);// 递归处理基准右边的部分}privatestaticintpartition(int[]arr,intleft,intright){intpivotarr[left];// 把左边第一个数当基准挖走它left位置就是第一个坑intileft;// i左指针始终指向当前坑的位置intjright;// j右指针从右端开始往左扫while(ij){// ① 右指针先动基准选左边时铁律从右往左找第一个 ≤ 基准的数while(ijarr[j]pivot)j--;// 找到了把 arr[j] 填进左边的坑然后 i 右移j 变成新坑if(ij){arr[i]arr[j];i;}// ② 左指针从左往右找第一个 ≥ 基准的数while(ijarr[i]pivot)i;// 找到了把 arr[i] 填进右边的坑然后 j 左移i 变成新坑if(ij){arr[j]arr[i];j--;}}// i j指针相遇当前位置就是基准的最终归宿回填基准值arr[i]pivot;returni;// 返回基准下标用于划分左右子区间}}注意事项填坑前必须判断i j否则指针相遇后还在赋值数组会乱基准选左边 → 必须先动右指针这是铁律背下来反之就是基准选右边→必须先动左指针逻辑清晰面试讲解首选这个写法三、双指针交换法进阶常用/面试用思路不挖坑了双指针直接找错位元素互换。右指针找小的左指针找大的找到就交换最后把基准换到分界点。比挖坑法代码更短工程中更常见。过程演示以[5, 2, 9, 3, 8]为例基准 5i 0, j length - 1初始[5, 2, 9, 3, 8] pivot5 i j 第1步j从右找 ≤5找到 arr[3]3停下 i从左找 5找到 arr[2]9停下 交换 arr[2] 和 arr[3] [5, 2, 3, 9, 8]已经交换过了 i j 第2步j继续左移找 ≤5j2arr[2]3 ≤5停下 i继续右移找 5i3i j退出循环 最终j2 是分界点交换 arr[0] 和 arr[2] [3, 2, 5, 9, 8] ↑ 基准归位关键退出循环后和 j 交换不是 i。关键原因j 是左区间最后一个 ≤ 基准的位置。完整代码publicclassQuickSortSwap{publicstaticvoidmain(String[]args){int[]arr{5,2,9,3,8,4,1,7,6};quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}privatestaticvoidquickSort(int[]arr,intleft,intright){if(leftright)return;// 区间只剩0或1个元素直接返回intpivotIndexpartition(arr,left,right);// 分区获取基准最终位置quickSort(arr,left,pivotIndex-1);// 递归左半部分quickSort(arr,pivotIndex1,right);// 递归右半部分}privatestaticintpartition(int[]arr,intleft,intright){intpivotarr[left];// 选左边界为基准intileft;// 左指针从左端出发往右找大数intjright;// 右指针从右端出发往左找小数while(ij){// ① 右指针先动从右往左找第一个 ≤ 基准的数找到小数while(ijarr[j]pivot)j--;// ② 左指针从左往右找第一个 基准的数找到大数while(ijarr[i]pivot)i;// 两个错位元素都找到了直接交换各回各位if(ij)swap(arr,i,j);}// 循环结束时 i jj 是左区间最后一个 ≤ 基准的位置分界点// 把基准从 left 换到分界点 j基准正式归位// 注意这里必须和 j 交换不能和 i 交换swap(arr,left,j);returnj;// 返回基准下标}privatestaticvoidswap(int[]arr,inta,intb){inttemparr[a];arr[a]arr[b];arr[b]temp;}}挖坑法 vs 双指针交换法对比项挖坑法双指针交换法代码量稍多更简洁理解难度低适合入门稍高面试讲解逻辑清晰好解释写起来更快推荐场景初学、讲解熟练后日常使用面试用四、单指针法最简单零困惑思路换个角度不用双指针来回移动改用一个指针p标记小于等于基准的区域的边界。遍历数组遇到 ≤ 基准的数就把它划入左区域遍历完把基准放到分界点。基准选右边界完全不用考虑指针先后顺序问题。过程演示以[5, 2, 9, 3, 8]为例基准 8右边界初始p -1左区域为空 i0, arr[0]5 ≤ 8p0交换arr[0]和arr[0][5, 2, 9, 3, 8] i1, arr[1]2 ≤ 8p1交换arr[1]和arr[1][5, 2, 9, 3, 8] i2, arr[2]9 8跳过 i3, arr[3]3 ≤ 8p2交换arr[2]和arr[3][5, 2, 3, 9, 8] 遍历结束基准换到 p13 的位置 结果[5, 2, 3, 8, 9] ↑ 基准归位完整代码publicclassQuickSortSinglePointer{publicstaticvoidmain(String[]args){int[]arr{5,2,9,3,8,4,1,7,6};quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}privatestaticvoidquickSort(int[]arr,intleft,intright){if(leftright)return;// 区间只剩0或1个元素直接返回intpivotIndexpartition(arr,left,right);// 分区quickSort(arr,left,pivotIndex-1);// 递归左边quickSort(arr,pivotIndex1,right);// 递归右边}privatestaticintpartition(int[]arr,intleft,intright){intpivotarr[right];// 选右边界为基准这样就不用管指针先后顺序了intpleft-1;// p 是小于等于基准的区域的右边界初始在区间外// 遍历 left 到 right-1不包括基准本身for(intileft;iright;i){if(arr[i]pivot){p;// 左区域扩大一格swap(arr,p,i);// 把当前元素换进左区域}// 如果 arr[i] pivot直接跳过它自然就在右区域}// 遍历结束p1 就是基准应该待的位置// 把基准从右边界换过来正式归位swap(arr,p1,right);returnp1;// 返回基准下标}privatestaticvoidswap(int[]arr,inta,intb){inttemparr[a];arr[a]arr[b];arr[b]temp;}}这个写法是 LeetCode 官方题解里最常见的风格刷题时经常能看到。五、趣味版Python 一行快排学了这么多来个解压的。Python 一行代码实现快排defquick_sort(arr):iflen(arr)1:returnarrelse:returnquick_sort([xforxinarr[1:]ifxarr[0]])[arr[0]]quick_sort([xforxinarr[1:]ifxarr[0]])print(quick_sort([5,2,9,3,8,4,1,7,6]))# [1, 2, 3, 4, 5, 6, 7, 8, 9]拆解一下arr[0] → 基准第一个元素 arr[1:] arr[0] → 左边比基准小的 arr[1:] arr[0] → 右边比基准大的 递归拼接三部分 → 排好了优点写起来爽面试秀一下没问题。缺点每次都创建新数组空间复杂度 O(n)不是原地排序实际项目别用。六、核心考点速查时间复杂度情况复杂度什么时候发生平均O(n log n)正常情况基准每次大致把数组对半分最坏O(n²)数组本来就有序每次基准都选到最大或最小值分区极度不均匀空间O(log n)递归调用栈不是额外数组深度等于递归层数最坏情况怎么避免数组有序时快排会退化成 O(n²)两种常见优化随机选基准每次从区间里随机挑一个数当基准打破有序的陷阱三数取中取arr[left]、arr[mid]、arr[right]三个数的中间值当基准比随机更稳定稳定性快排是不稳定排序。什么叫不稳定举个例子数组里有两个 5排序前第一个 5 在第二个 5 左边排完之后顺序可能反了。如果业务要求相同元素保持原来的相对顺序用归并排序不要用快排。面试最容易写错的三个地方① 递归终止条件别漏当外层循环里面是true的时候内层必须写下面这段代码来跳出循环。当外层循环是i j的时候就不用写if(leftright)return;漏了这行递归永远不停直接栈溢出。用而不是因为边界情况下 left 可能超过 right。② 基准选左边必须先动右指针原因基准挖走后left 位置是空坑。如果先动左指针左指针找到大数填到右边左边坑消失了但基准还没归位数组就乱了。先动右指针保证左边的坑始终存在基准最后才能安全回填。反过来同样成立基准选右边 → 必须先动左指针。③ 交换法最后和 j 交换不是 i退出循环时 i j此时j 停在左区间最后一个 ≤ 基准的位置分界点i 停在右区间第一个 基准的位置基准要放在分界点所以和 j 交换。如果和 i 交换基准会跑到右区间里分区就错了。三种写法对比写法难度代码量推荐场景挖坑法⭐⭐中入门学习双指针交换法⭐⭐⭐少熟练后日常使用面试用单指针法⭐最少刷题、快速手写作者[识君啊]