计算机基础学习 第六天笔记 基数排序，归并排序和快速排序

📚 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];
}
}

// 计算最大值的位数，即需要进行几轮排序
// 例如：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)

• 核心思想：采用“分治法”思想，核心是“合并有序列”。算法分为“拆分”和“合并”两个阶段。
• 实现步骤：
• 拆分 (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. 递归拆分右半部分：[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），将数组划分为两部分，左边都比基准数小，右边都比基准数大。
• 实现步骤：
• 选择基准：通常选择当前排序区间的第一个元素作为基准数（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到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);
}
}