企业官网建设流程全解析

📚 7月22日课程复习笔记：高级排序算法深度解析

本次课程深入探讨了三种高效排序算法：基数排序、归并排序和快速排序。课程不仅讲解了它们的分治思想和实现细节，还通过绘制内存图的方式，深入剖析了递归调用过程中的栈与堆内存变化，并对归并排序与快速排序进行了详细对比。

第一部分：基数排序与归并排序

1. 基数排序 (Radix Sort)

• 核心思想：一种非比较排序算法，利用数字各位的权重进行排序。它通过“分配”和“收集”的过程，从最低位（个位）到最高位依次对数据进行排序。
• 实现步骤：
  1. 准备桶：创建10个桶（0-9），对应十进制数的每一位可能取值。
  2. 按位排序：从个位开始，根据每个数字当前位的值，将其放入对应的桶中。
  3. 收集数据：按照桶的顺序（0到9），依次将桶内数据取出，重新组合成数组。
  4. 重复操作：对十位、百位等更高位重复上述“分配-收集”过程，直到处理完最高位。
• 稳定性：基数排序是稳定的。在处理某一位时，相同位数的数字会保持上一轮排序的相对顺序。
• 时间复杂度：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]; } } // 计算最大值的位数，即需要进行几轮排序 // 例如：maxcount=422，则maxnum=3，需要排3轮（个位、十位、百位） int maxnum = (maxcount + "").length(); int n = 1; // n=1表示个位，n=10表示十位，n=100表示百位... // 外层循环：按位数进行排序，从个位开始到最高位 for(int m = 0; m < maxnum; m++) { // 第一步：将数组元素按当前位数的数字分配到对应的桶中 for(int j = 0; j < arr.length; j++) { // 计算当前元素在当前位数上的数字（0-9） // 例如：arr[j]=422, n=1时取个位2；n=10时取十位2；n=100时取百位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)

• 核心思想：采用“分治法”思想，核心是“合并有序列”。算法分为“拆分”和“合并”两个阶段。
• 实现步骤：
  1. 拆分 (Divide)：使用递归将待排序数组不断从中间一分为二，直到每个子数组只包含一个元素（此时视为有序）。
  2. 合并 (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. 递归拆分右半部分：[mid+1, 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. 递归拆分右半部分：[mid+1, right] split(arr, mid + 1, right); // 4. 【关键步骤】左右两部分都拆分完毕后，调用合并方法 // 将两个已经有序的子数组 [left, mid] 和 [mid+1, 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），将数组划分为两部分，左边都比基准数小，右边都比基准数大。
• 实现步骤：
  1. 选择基准：通常选择当前排序区间的第一个元素作为基准数（Pivot）。
  2. 双指针分区：
     • 使用两个指针i（从左向右）和j（从右向左）。
     • j指针先移动，寻找比基准数小的元素。
     • i指针后移动，寻找比基准数大的元素。
     • 当i和j都找到目标且未相遇时，交换i和j位置的元素。
  3. 基准归位：当i和j相遇时，将基准数与相遇点的元素交换。此时，基准数已到达其在最终有序数组中的正确位置。
  4. 递归排序：以基准数的位置为界，对其左右两个子数组分别递归执行快速排序。
• 时间复杂度：
  • 平均情况：O(N log N)。
  • 最坏情况：O(N²)。当数组本身已有序或逆序时，每次分区都极不均衡，导致递归深度达到N。
• 空间复杂度：主要是递归调用栈的开销，平均为O(log N)，最坏为O(N)。

2. 归并排序与快速排序对比

• 稳定性：归并排序是稳定的，快速排序是不稳定的。
• 空间使用：归并排序需要O(N)的额外辅助空间；快速排序是原地排序，空间复杂度更低。
• 递归顺序：归并排序是“先递归拆分到底，再回溯合并”；快速排序是“先分区确定一个元素位置，再递归处理两边”。
• 边界处理：
  • 归并排序：通过mid划分区间（left到mid，mid+1到right），天然保证了边界安全，递归终止条件只需判断left == right。
  • 快速排序：分区后递归调用时，边界为left到i-1和i+1到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(left>=right) { return; } int base=arr[left]; int i=left; int j=right; while(i!=j) { while(i!=j&& arr[j]>=base) { j--; } while(i!=j&& arr[i]<=base) { i++; } int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } arr[left]=arr[i]; arr[i]=base; sort(arr,left,i-1); sort(arr,i+1,right); } }