快速排序和堆排序

摘要：本文详细介绍了两种高效的排序算法——快速排序和堆排序。快速排序采用分治思想，通过挖坑分区法实现，平均时间复杂度为 O(n log n)；堆排序基于完全二叉树的堆结构，通过构建大顶堆和交换堆顶元素实现排序，时间复杂度稳定为 O(n log n)。两种算法均为原地排序，但都不稳定。

快速排序(quickSort)

算法核心：快速排序采用区间首个元素作为基准值，利用左右双指针交替移动的挖坑分区思路，右指针先向左搜寻小于基准的元素填入左侧坑位，再让左指针向右搜寻大于基准的元素填入右侧坑位，两指针相遇时将基准放入相遇位置完成分区，再通过递归分别对基准值的左右两侧子区间重复分区操作，依靠分治思想逐步完成整个数组的升序排序。

核心要点

1. 基准选取：区间最左侧元素作为 pivot，把 l 下标位置当成第一个 “坑”，暂存 pivot；
2. 双指针分区：右指针 h 向左找小数填左坑，左指针 l 向右找大数填右坑，交替填坑；
3. 基准归位：l 与 h 相遇时，只剩唯一坑位，放入 pivot，此时左边≤pivot、右边≥pivot；
4. 递归分治：以 pivot 下标分割数组，分别递归排序左、右子区间，直至区间只剩 1 个元素。

算法步骤

1. 保存基准值pivot = arr[l]；
2. 循环：当l < h未相遇
   ① h 往左走，找到第一个小于 pivot 的元素，填入 l 的坑，此时 h 变为新坑；
   ② l 往右走，找到第一个大于 pivot 的元素，填入 h 的坑，此时 l 变为新坑；
3. l == h，把 pivot 填入该坑，返回当前下标（基准最终位置）；
4. 递归处理左段[l, pivot下标-1]、右段[pivot下标+1, h]；
5. 递归终止条件：区间l >= h，无需排序直接返回。

算法特点
时间复杂度：(O(nlog n))
空间复杂度：(O(log n))
稳定性：不稳定算法（相等元素可能会改变相对位置）

Java语言实现

packagecom.lgq.ruankao.practice;importstaticcom.lgq.ruankao.util.ArrUtil.printArr;importstaticcom.lgq.ruankao.util.ArrUtil.swap;/** * @author lgq * @email * @date 2026/8/13 9:35 */publicclassMain3{publicstaticvoidquickSort(int[]arr,intl,inth){if(l>=h)return;// 获取基准值pivot在序列中分割后的下标(经过一次快速排序后，pivot的下标)intpivotIndex=partition(arr,l,h);// 分治思想：递归排序左区间quickSort(arr,l,pivotIndex-1);quickSort(arr,pivotIndex+1,h);}// 分区函数，选取最右边元素作为基准值，划分大小区域// 简单说就是，选择最右边元素作为基准值，进行一趟快速排序，最后将pivot值的下标返回privatestaticintpartition(int[]arr,intl,inth){// 选取第一个元素作为基准值intpivot=arr[l];while(l<h){// 1. 右指针h向左找小于pivot的元素，找到就交换l和h指针指向的元素while(l<h&&arr[h]>=pivot){h--;}// 退出while循环表示找到了，此时需要将右边的值赋值给左边，覆盖掉左边的值arr[l]=arr[h];// 2. 左指针l向右寻找大于pivot的数while(l<h&&arr[l]<=pivot){l++;}// 找到大于pivot的元素了，此时需要将左边的值赋值给右边，覆盖掉右边的值arr[h]=arr[l];}// 最后当l == h时，此时就是基准值pivot在一趟快速排序后的最终位置下标了，进行赋值即可。arr[l]=pivot;// 或者，因为此时，arr[l] == arr[h]// arr[h] = pivot;returnl;}// 测试publicstaticvoidmain(String[]args){int[]arr={5,2,9,3,7,6,1,8,4};System.out.println("排序前：");printArr(arr);quickSort(arr,0,arr.length-1);System.out.println("排序后：");printArr(arr);}}

交换和打印函数

packagecom.lgq.ruankao.util;/** * @author lgq * @email * @date 2026/8/12 9:34 */publicclassArrUtil{publicstaticvoidprintArr(int[]arr){if(arr==null||arr.length<1){return;}for(inti=0;i<arr.length;i++){System.out.print(arr[i]+" ");}System.out.println();}// 交换a和b的值publicstaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}

堆排序

堆的定义：堆是完全二叉树，分为两种：

1. 大顶堆：每个父节点值 ≥ 左右子节点值；堆顶是整个序列最大值。
2. 小顶堆：每个父节点值 ≤ 左右子节点值；堆顶是整个序列最小值。

一般，堆排序默认使用大顶堆实现升序排序。

算法的核心思想：

1. 将无序数组构建成大顶堆；此时堆顶（数组第一个元素）是最大值。
2. 把堆顶最大值和数组末尾元素交换，最大值落到有序末尾。
3. 对剩余未排序部分重新调整为大顶堆，重复交换堆顶与末尾。
4. 不断缩小区间，直到整个数组有序。

算法特点：
时间复杂度：最好 /最坏 / 平均均为 (O(nlog n))
空间复杂度：(O(1))，原地排序
不稳定排序：（相等元素相对位置会改变）

数组与堆节点下标关系：
设父节点下标为i：

• 左孩子：2*i + 1
• 右孩子：2*i + 2
• 最后一个非叶子节点：⌊n/2⌋ - 1（n 为数组长度）

Java语言编程实现

packagecom.lgq.ruankao.practice;importstaticcom.lgq.ruankao.util.ArrUtil.printArr;importstaticcom.lgq.ruankao.util.ArrUtil.swap;/** * @author lgq * @email * @date 2026/8/13 15:22 */publicclassMain4{/** * 堆调整：维护大顶堆性质 * * @param arr 数组 * @param n 堆有效长度 * @param i 当前父节点下标 */publicstaticvoidheapAdjust(int[]arr,intn,inti){intmaxValueIndex=i;// 左右孩子下标intleftIndex=2*i+1;intrightIndex=2*i+2;// 判断左节点值更大if(leftIndex<n&&arr[leftIndex]>arr[maxValueIndex]){maxValueIndex=leftIndex;}// 判断右节点值更大if(rightIndex<n&&arr[rightIndex]>arr[maxValueIndex]){maxValueIndex=rightIndex;}// 如果最大值不是父节点，就交换if(maxValueIndex!=i){swap(arr,i,maxValueIndex);// 递归调整受影响的子树heapAdjust(arr,n,maxValueIndex);}}/** * 堆排序主方法，升序 */publicstaticvoidheapSort(int[]arr){intn=arr.length;if(n<=1)return;// 构造大顶堆，从最后一个非叶子节点开始向前遍历for(inti=n/2-1;i>=0;i--){heapAdjust(arr,n,i);}// 逐个取出堆顶最大值放到数组末尾for(inti=n-1;i>0;i--){swap(arr,0,i);// 调整剩余未排序区间,[0, i-1]heapJustify(arr,i,0);}}publicstaticvoidmain(String[]args){// 测试用例1：普通乱序数组int[]arr1={12,11,13,5,6,7};System.out.print("排序前：");printArr(arr1);heapSort(arr1);System.out.print("排序后：");printArr(arr1);System.out.println("------------------------");// // 测试用例2：逆序数组// int[] arr2 = {9,7,5,3,1};// System.out.print("排序前：");// printArr(arr2);// heapSort(arr2);// System.out.print("排序后：");// printArr(arr2);// System.out.println("------------------------");//// // 测试用例3：存在重复值// int[] arr3 = {2,5,3,2,9,5,1};// System.out.print("排序前：");// printArr(arr3);// heapSort(arr3);// System.out.print("排序后：");// printArr(arr3);}}