【第六篇】Java 基础排序算法：快速排序算法和堆排序

快速排序和堆排序摘要本文详细介绍了两种高效的排序算法——快速排序和堆排序。快速排序采用分治思想通过挖坑分区法实现平均时间复杂度为 O(n log n)堆排序基于完全二叉树的堆结构通过构建大顶堆和交换堆顶元素实现排序时间复杂度稳定为 O(n log n)。两种算法均为原地排序但都不稳定。快速排序(quickSort)算法核心快速排序采用区间首个元素作为基准值利用左右双指针交替移动的挖坑分区思路右指针先向左搜寻小于基准的元素填入左侧坑位再让左指针向右搜寻大于基准的元素填入右侧坑位两指针相遇时将基准放入相遇位置完成分区再通过递归分别对基准值的左右两侧子区间重复分区操作依靠分治思想逐步完成整个数组的升序排序。核心要点基准选取区间最左侧元素作为 pivot把 l 下标位置当成第一个 “坑”暂存 pivot双指针分区右指针 h 向左找小数填左坑左指针 l 向右找大数填右坑交替填坑基准归位l 与 h 相遇时只剩唯一坑位放入 pivot此时左边≤pivot、右边≥pivot递归分治以 pivot 下标分割数组分别递归排序左、右子区间直至区间只剩 1 个元素。算法步骤保存基准值pivot arr[l]循环当l h未相遇① h 往左走找到第一个小于 pivot 的元素填入 l 的坑此时 h 变为新坑② l 往右走找到第一个大于 pivot 的元素填入 h 的坑此时 l 变为新坑l h把 pivot 填入该坑返回当前下标基准最终位置递归处理左段[l, pivot下标-1]、右段[pivot下标1, h]递归终止条件区间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(lh)return;// 获取基准值pivot在序列中分割后的下标(经过一次快速排序后pivot的下标)intpivotIndexpartition(arr,l,h);// 分治思想递归排序左区间quickSort(arr,l,pivotIndex-1);quickSort(arr,pivotIndex1,h);}// 分区函数选取最右边元素作为基准值划分大小区域// 简单说就是选择最右边元素作为基准值进行一趟快速排序最后将pivot值的下标返回privatestaticintpartition(int[]arr,intl,inth){// 选取第一个元素作为基准值intpivotarr[l];while(lh){// 1. 右指针h向左找小于pivot的元素找到就交换l和h指针指向的元素while(lharr[h]pivot){h--;}// 退出while循环表示找到了此时需要将右边的值赋值给左边覆盖掉左边的值arr[l]arr[h];// 2. 左指针l向右寻找大于pivot的数while(lharr[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(arrnull||arr.length1){return;}for(inti0;iarr.length;i){System.out.print(arr[i] );}System.out.println();}// 交换a和b的值publicstaticvoidswap(int[]arr,inti,intj){inttemparr[i];arr[i]arr[j];arr[j]temp;}}堆排序堆的定义堆是完全二叉树分为两种大顶堆每个父节点值 ≥ 左右子节点值堆顶是整个序列最大值。小顶堆每个父节点值 ≤ 左右子节点值堆顶是整个序列最小值。一般堆排序默认使用大顶堆实现升序排序。算法的核心思想将无序数组构建成大顶堆此时堆顶数组第一个元素是最大值。把堆顶最大值和数组末尾元素交换最大值落到有序末尾。对剩余未排序部分重新调整为大顶堆重复交换堆顶与末尾。不断缩小区间直到整个数组有序。算法特点时间复杂度最好 /最坏 / 平均均为 (O(nlog n))空间复杂度(O(1))原地排序不稳定排序相等元素相对位置会改变数组与堆节点下标关系设父节点下标为i左孩子2*i 1右孩子2*i 2最后一个非叶子节点⌊n/2⌋ - 1n 为数组长度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){intmaxValueIndexi;// 左右孩子下标intleftIndex2*i1;intrightIndex2*i2;// 判断左节点值更大if(leftIndexnarr[leftIndex]arr[maxValueIndex]){maxValueIndexleftIndex;}// 判断右节点值更大if(rightIndexnarr[rightIndex]arr[maxValueIndex]){maxValueIndexrightIndex;}// 如果最大值不是父节点就交换if(maxValueIndex!i){swap(arr,i,maxValueIndex);// 递归调整受影响的子树heapAdjust(arr,n,maxValueIndex);}}/** * 堆排序主方法升序 */publicstaticvoidheapSort(int[]arr){intnarr.length;if(n1)return;// 构造大顶堆从最后一个非叶子节点开始向前遍历for(intin/2-1;i0;i--){heapAdjust(arr,n,i);}// 逐个取出堆顶最大值放到数组末尾for(intin-1;i0;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);}}