7月22日课程复习笔记高级排序算法深度解析本次课程深入探讨了三种高效排序算法基数排序、归并排序和快速排序。课程不仅讲解了它们的分治思想和实现细节还通过绘制内存图的方式深入剖析了递归调用过程中的栈与堆内存变化并对归并排序与快速排序进行了详细对比。第一部分基数排序与归并排序1. 基数排序 (Radix Sort)核心思想一种非比较排序算法利用数字各位的权重进行排序。它通过“分配”和“收集”的过程从最低位个位到最高位依次对数据进行排序。实现步骤准备桶创建10个桶0-9对应十进制数的每一位可能取值。按位排序从个位开始根据每个数字当前位的值将其放入对应的桶中。收集数据按照桶的顺序0到9依次将桶内数据取出重新组合成数组。重复操作对十位、百位等更高位重复上述“分配-收集”过程直到处理完最高位。稳定性基数排序是稳定的。在处理某一位时相同位数的数字会保持上一轮排序的相对顺序。时间复杂度O(K * N)其中N是数据量K是数据的最大位数。当K远小于N时效率极高接近O(N)。适用场景适用于数据量大但数值位数不高的正整数排序场景。package com.sort.study; import java.util.Arrays; public class JishuSort { public static void main(String[] args) { int[] arr {222,11,422,5,12,42,191,19,8,1,0}; sort(arr); System.out.println(Arrays.toString(arr)); } /** * 基数排序Radix Sort * 这是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字 * 然后按每个位数分别比较。 * * 算法步骤LSD最低位优先 * 1. 找出数组中最大的数确定最大位数 * 2. 从个位开始按照当前位的数字将元素分配到对应的桶中 * 3. 按顺序从桶中取出元素放回原数组 * 4. 重复步骤2-3处理十位、百位...直到最高位 * * param arr 待排序的整数数组 */ public static void sort(int[] arr) { // 创建10个桶对应数字0-9每个桶最多存放arr.length个元素 int[][] bucket new int[10][arr.length]; // 桶计数器记录每个桶中当前存放的元素个数 int[] bucketcount new int[10]; // 找出数组中的最大值用于确定需要排序的位数 int maxcount arr[0]; for(int i 0; i arr.length; i) { if(arr[i] maxcount) { maxcount arr[i]; } } // 计算最大值的位数即需要进行几轮排序 // 例如maxcount422则maxnum3需要排3轮个位、十位、百位 int maxnum (maxcount ).length(); int n 1; // n1表示个位n10表示十位n100表示百位... // 外层循环按位数进行排序从个位开始到最高位 for(int m 0; m maxnum; m) { // 第一步将数组元素按当前位数的数字分配到对应的桶中 for(int j 0; j arr.length; j) { // 计算当前元素在当前位数上的数字0-9 // 例如arr[j]422, n1时取个位2n10时取十位2n100时取百位4 int element arr[j] / n % 10; // 获取该数字对应的桶中已有元素个数 int count bucketcount[element]; // 将当前元素放入对应的桶中 bucket[element][count] arr[j]; // 该桶的元素计数加1 bucketcount[element]; } // 第二步按顺序从桶中取出所有元素放回原数组 int index 0; // 原数组的索引指针 // 遍历所有桶0-9号桶 for(int k 0; k bucketcount.length; k) { // 如果当前桶中有元素则依次取出 for(int h 0; h bucketcount[k]; h) { arr[index] bucket[k][h]; // 从桶中取出元素 index; // 原数组索引后移 } // 取出完毕后将桶计数器清零为下一轮排序做准备 bucketcount[k] 0; } // n乘以10准备处理下一位个位→十位→百位→千位... n n * 10; } } }2. 归并排序 (Merge Sort)核心思想采用“分治法”思想核心是“合并有序列”。算法分为“拆分”和“合并”两个阶段。实现步骤拆分 (Divide)使用递归将待排序数组不断从中间一分为二直到每个子数组只包含一个元素此时视为有序。合并 (Conquer)自底向上地将两个相邻的有序子数组合并成一个更大的有序数组。合并操作细节双指针技术使用两个指针s1, s2分别指向两个待合并的有序子数组的起始位置。比较写入比较两个指针所指的元素将较小的元素写入一个临时数组并移动对应指针。处理剩余当一个子数组的元素全部写入后将另一个子数组的剩余元素直接追加到临时数组末尾。数据回写将临时数组中的有序数据写回原数组的对应位置。注意写回的起始位置是原数组的left边界而非临时数组的0下标。时间复杂度稳定为O(N log N)。无论数据初始状态如何都需要进行log₂N层拆分每层合并操作的总耗时为O(N)。空间复杂度需要O(N)的额外空间来创建临时数组。package com.sort.study; import java.util.Arrays; /** * 归并排序Merge Sort * 核心思想分治Divide and Conquer * 时间复杂度O(n log n)无论最好、最坏、平均情况都稳定 * 空间复杂度O(n)需要额外临时数组 * 稳定性稳定排序相等元素保持原顺序 */ public class GuibingSort { public static void main(String[] args) { // 1. 定义测试数组 int[] arr {222, 11, 422, 5, 12, 42, 191, 19, 8, 1, 0}; // 2. 调用拆分方法对整个数组进行归并排序 // 参数说明arr-待排序数组0-左边界起始索引arr.length-1-右边界结束索引 split(arr, 0, arr.length - 1); // 3. 输出排序后的结果 System.out.println(Arrays.toString(arr)); // 预期输出[0, 1, 5, 8, 11, 12, 19, 42, 191, 222, 422] } /** * 【分治阶段 - 拆分方法】 * 功能递归地将数组从中间一分为二直到每个子数组只剩一个元素 * * 执行流程 * 1. 如果 left right说明当前子数组只有一个元素直接返回递归终止 * 2. 计算中间位置 mid将数组分成左右两半 * 3. 递归拆分左半部分[left, mid] * 4. 递归拆分右半部分[mid1, right] * 5. 左右两部分都拆分完毕后调用 merge 方法合并两个有序子数组 * * param arr 待排序的数组 * param left 当前子数组的左边界索引起始位置 * param right 当前子数组的右边界索引结束位置 */ public static void split(int[] arr, int left, int right) { // 【递归终止条件】如果左右边界相等说明当前子数组只有一个元素 // 单个元素天然有序无需继续拆分直接返回 if (left right) { return; } // 1. 计算中间位置防止整数溢出也可写为 left (right - left) / 2 int mid (left right) / 2; // 2. 递归拆分左半部分[left, mid] split(arr, left, mid); // 3. 递归拆分右半部分[mid1, right] split(arr, mid 1, right); // 4. 【关键步骤】左右两部分都拆分完毕后调用合并方法 // 将两个已经有序的子数组 [left, mid] 和 [mid1, right] 合并成一个有序数组 merge(arr, left, mid, right); } /** * 【治理阶段 - 合并方法】 * 功能将两个已经有序的子数组合并成一个有序的大数组 * * 合并思路双指针法 * 1. 用 s1 指向左子数组第一个元素s2 指向右子数组第一个元素 * 2. 比较 arr[s1] 和 arr[s2]将较小的放入临时数组 * 3. 指针后移继续比较直到某个子数组全部放入临时数组 * 4. 将剩余子数组的元素全部拷贝到临时数组 * 5. 将临时数组的有序结果复制回原数组的对应位置 * * param arr 原数组 * param left 左子数组的起始位置 * param mid 左子数组的结束位置也是中间分割点 * param right 右子数组的结束位置 */ public static void merge(int[] arr, int left, int mid, int right) { // 【步骤1】初始化指针 // s1左子数组的起始指针指向左半部分的第一个元素 int s1 left; // s2右子数组的起始指针指向右半部分的第一个元素 int s2 mid 1; // 【步骤2】创建临时数组 // 长度 当前待合并的两个子数组的总长度 // temp 用于存放合并后的有序结果 int[] temp new int[right - left 1]; // index临时数组的当前填充位置从 0 开始 int index 0; // 【步骤3】两路归并 - 核心比较逻辑 // 循环条件左右两个子数组都还有元素未处理s1 mid 且 s2 right while (s1 mid s2 right) { // 比较左右两个子数组的当前元素 if (arr[s1] arr[s2]) { // 如果左子数组的当前元素 小于 右子数组的当前元素 // 将左子数组的元素放入临时数组 temp[index] arr[s1]; s1; // 左指针右移指向下一个元素 index; // 临时数组填充位置后移 } else { // 否则arr[s1] arr[s2]将右子数组的元素放入临时数组 temp[index] arr[s2]; s2; // 右指针右移指向下一个元素 index; // 临时数组填充位置后移 } } // 【步骤4】处理剩余元素 // 当上面的 while 循环结束时至少有一个子数组已经全部放入临时数组 // 情况1如果左子数组还有剩余元素s1 mid 成立 // 说明右子数组已经全部放入临时数组了 // 直接将左子数组的剩余元素全部拷贝到临时数组 while (s1 mid) { temp[index] arr[s1]; s1; index; } // 情况2如果右子数组还有剩余元素s2 right 成立 // 说明左子数组已经全部放入临时数组了 // 直接将右子数组的剩余元素全部拷贝到临时数组 while (s2 right) { temp[index] arr[s2]; s2; index; } // 【步骤5】将合并结果写回原数组 // 将临时数组中排好序的所有元素复制回原数组的对应位置 // 注意原数组的起始位置是 left所以目标位置是 arr[left i] for (int i 0; i temp.length; i) { arr[left i] temp[i]; } // 至此[left, right] 范围内的元素已经有序 } }第二部分快速排序与算法对比1. 快速排序 (Quick Sort)核心思想同样采用“分治法”核心是“分区 (Partition)”。通过选择一个基准数Pivot将数组划分为两部分左边都比基准数小右边都比基准数大。实现步骤选择基准通常选择当前排序区间的第一个元素作为基准数Pivot。双指针分区使用两个指针i从左向右和j从右向左。j指针先移动寻找比基准数小的元素。i指针后移动寻找比基准数大的元素。当i和j都找到目标且未相遇时交换i和j位置的元素。基准归位当i和j相遇时将基准数与相遇点的元素交换。此时基准数已到达其在最终有序数组中的正确位置。递归排序以基准数的位置为界对其左右两个子数组分别递归执行快速排序。时间复杂度平均情况O(N log N)。最坏情况O(N²)。当数组本身已有序或逆序时每次分区都极不均衡导致递归深度达到N。空间复杂度主要是递归调用栈的开销平均为O(log N)最坏为O(N)。2. 归并排序与快速排序对比稳定性归并排序是稳定的快速排序是不稳定的。空间使用归并排序需要O(N)的额外辅助空间快速排序是原地排序空间复杂度更低。递归顺序归并排序是“先递归拆分到底再回溯合并”快速排序是“先分区确定一个元素位置再递归处理两边”。边界处理归并排序通过mid划分区间left到midmid1到right天然保证了边界安全递归终止条件只需判断left right。快速排序分区后递归调用时边界为left到i-1和i1到right。必须增加left right的判断防止因i-1小于left而导致数组下标越界。Java应用Arrays.sort()方法的底层实现就是经过优化的快速排序。package com.sort.study; import java.util.Arrays; public class KuaisuSort { public static void main(String[] args) { int[] arr {222,11,422,5,12,42,191,19,8,1,0}; sort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr, int left, int right) { if(leftright) { return; } int basearr[left]; int ileft; int jright; while(i!j) { while(i!j arr[j]base) { j--; } while(i!j arr[i]base) { i; } int temparr[i]; arr[i]arr[j]; arr[j]temp; } arr[left]arr[i]; arr[i]base; sort(arr,left,i-1); sort(arr,i1,right); } }