排序算法分类详解

// 三种 O(n²) 排序的核心操作对比

// 冒泡排序：相邻元素比较交换
for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            swap(arr, j, j + 1);  // 频繁交换
        }
    }
}

// 选择排序：选择最值放到已排序区
for (int i = 0; i < n - 1; i++) {
    int minIdx = i;
    for (int j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIdx]) {
            minIdx = j;  // 只记录索引，不交换
        }
    }
    swap(arr, i, minIdx);  // 每轮只交换一次
}

// 插入排序：将元素插入已排序区
for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];  // 移动元素
        j--;
    }
    arr[j + 1] = key;  // 插入
}

// 计数排序：适合数据范围小
int[] arr = {4, 2, 2, 8, 3, 3, 1};  // 范围 1-8，适合
int[] arr2 = {1, 1000000, 2};        // 范围大，不适合

// 桶排序：适合数据分布均匀
float[] arr = {0.42f, 0.32f, 0.33f, 0.52f};  // 0-1 均匀分布，适合

// 基数排序：适合固定位数整数
int[] arr = {170, 45, 75, 90, 802};  // 3位数以内，适合
String[] arr = {"cat", "bat", "rat"}; // 等长字符串，适合

// 计数排序：统计每个值的出现次数
值:    1  2  2  3  3  3  4
计数:  0  1  2  3  1  ...
          ↓
排序:  1, 2, 2, 3, 3, 3, 4

// 桶排序：将数据分到多个桶，桶内再排序
数据: [0.42, 0.32, 0.33, 0.52, 0.37, 0.47]
桶0: [0.32, 0.33, 0.37]  → 排序
桶1: [0.42, 0.47]        → 排序
桶2: [0.52]              → 已有序
          ↓
合并: [0.32, 0.33, 0.37, 0.42, 0.47, 0.52]

// 基数排序：按位排序（从低位到高位）
原始: [170, 45, 75, 90, 802, 24, 2, 66]
个位: [170, 90, 802, 2, 24, 45, 75, 66]
十位: [802, 2, 24, 45, 66, 170, 75, 90]
百位: [2, 24, 45, 66, 75, 90, 170, 802] ✓

// 学生记录，先按班级排序，再按成绩排序
class Student {
    String className;  // 班级
    int score;         // 成绩
}

// 原始数据（已按班级排序）
[张三-A班-85, 李四-A班-90, 王五-B班-85, 赵六-B班-90]

// 使用稳定排序按成绩排序后：
[张三-A班-85, 王五-B班-85, 李四-A班-90, 赵六-B班-90]
//     ↑ A班在前               ↑ A班在前（稳定性保证）

// 使用不稳定排序可能结果：
[王五-B班-85, 张三-A班-85, 赵六-B班-90, 李四-A班-90]
//     ↑ B班在前（相对顺序被打乱）

// 归并排序的稳定性保证
while (i < leftSize && j < rightSize) {
    // 使用 <= 而不是 <，保证相等元素左边先放入
    if (leftArr[i] <= rightArr[j]) {
        arr[k++] = leftArr[i++];
    } else {
        arr[k++] = rightArr[j++];
    }
}

// 基数排序的稳定性保证
// 从后向前遍历，保证相同值的元素保持原有顺序
for (int i = n - 1; i >= 0; i--) {
    int digit = (arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
}

// 选择排序的不稳定性示例
[4a, 4b, 3]  // 4a 和 4b 是值相等但身份不同的元素
    ↓
选择最小值 3，与 4a 交换
    ↓
[3, 4b, 4a]  // 4a 和 4b 的相对顺序改变了！

// 快速排序的不稳定性来源
// 分区过程中，相等元素的交换会打乱原有顺序
[3, 2, 4a, 5, 4b]
    ↓ 分区（pivot=4b）
[3, 2, 4a, 4b, 5]
    ↓ 递归排序
// 4a 和 4b 的相对位置可能改变

// 堆排序的不稳定性
// 堆调整过程中的元素交换会跨越多个位置

// 所有原地排序的共同特点
public static void sort(int[] arr) {
    // 只使用几个临时变量
    int temp, i, j;
    
    // 直接操作原数组
    for (i = 0; i < arr.length; i++) {
        // ... 排序逻辑
    }
    // 不需要额外的数组空间
}

// 归并排序：用 O(n) 空间换取稳定性和 O(n log n) 保证
// 适合：内存充足，需要稳定排序

// 计数排序：用 O(n + k) 空间换取 O(n) 时间
// 适合：数据范围小，追求极致速度

// 快速排序：用 O(log n) 栈空间换取平均最快性能
// 适合：通用场景，内存不敏感

// 案例 1：大规模用户数据排序（需要稳定性）
// 选择：归并排序或 Timsort
List<User> users = getUsers();  // 100万用户
users.sort(Comparator.comparing(User::getAge));  // Java 使用 Timsort

// 案例 2：实时数据流排序（数据逐个到达）
// 选择：插入排序
void onDataArrive(int value) {
    insertIntoSortedArray(arr, value);  // O(n) 插入
}

// 案例 3：考试成绩排序（0-100分）
// 选择：计数排序
int[] scores = getScores();  // 范围小
CountingSort.sort(scores);   // O(n)

// 案例 4：浮点数坐标排序（均匀分布）
// 选择：桶排序
float[] coordinates = getCoordinates();
BucketSort.sort(coordinates);  // 均匀分布时接近 O(n)

// 案例 5：内存极度受限的嵌入式系统
// 选择：堆排序或希尔排序
void sortInLimitedMemory(int[] arr) {
    HeapSort.sort(arr);  // O(1) 额外空间
}