#排序算法对比总结

// 不稳定排序的经典反例
// 原始：[{name: "A", score: 90}, {name: "B", score: 90}, {name: "C", score: 80}]
// 按分数降序排序后（不稳定）：
// 结果：[{name: "B", score: 90}, {name: "A", score: 90}, {name: "C", score: 80}]
// 注意：A和B的相对位置改变了！

// 稳定排序的结果应该是：
// 结果：[{name: "A", score: 90}, {name: "B", score: 90}, {name: "C", score: 80}]

// 场景：几十一百个元素的排序
// 推荐：插入排序

// 原因：
// 1. 小数据量时，O(n²) 和 O(nlogn) 差距不大
// 2. 插入排序的常数因子小
// 3. 插入排序对有序数组近乎 O(n)
insertionSort(arr);

// 场景：数组基本有序，只有少量乱序
// 推荐：插入排序

// 验证
int[] nearlySorted = {1, 3, 2, 4, 5, 6, 8, 7};
// 插入排序：只需交换几次，时间接近 O(n)

// 场景：排序后相同值的相对位置必须保持
// 推荐：归并排序

// 典型场景：
// 1. 按多个字段排序（先按A排，再按B排）
// 2. 数据库多字段排序
mergeSort(arr);  // 稳定排序

// 场景：大量随机数据的排序
// 推荐：快速排序（平均性能最好）

// 原因：
// 1. 平均 O(nlogn)
// 2. 原地排序，空间 O(logn)
// 3. 缓存友好
quickSort(arr);

// 场景：对性能要求严格，不能接受 O(n²) 的最坏情况
// 推荐：堆排序

// 特点：
// 1. 最坏情况也是 O(nlogn)
// 2. 原地排序，空间 O(1)
// 3. 但缓存不友好
heapSort(arr);

// 场景：整数排序，范围有限（如 0-10000）
// 推荐：计数排序

// 原因：O(n) 时间复杂度
int[] arr = {5, 2, 8, 1, 9, 3, 7, 4, 6};
countingSort(arr);  // O(n+k)，k是范围大小

// 场景：按字典序排序字符串
// 推荐：基数排序

// 原因：按字符逐位排序，适合等长字符串
radixSort(strings);

// Java 1.8+ 的实现策略
public static void sort(int[] a) {
    // 小数据量（< 47）：插入排序
    // 大数据量：TimSort（改进的归并排序）
    // 对于基本类型：用快速排序（不稳定但快）
    // 对于对象类型：用TimSort（稳定）
}

// 方案：改进的快速排序 + 插入排序
// 实际上Java对基本类型就是这么做的
// 虽然不稳定，但基本类型不需要稳定性

// 如果需要稳定，可以：
// 1. 用TimSort（Java对象排序）
// 2. 用归并排序（最坏情况也是 O(nlogn)）

// 场景：10GB数据排序，但内存只有1GB
// 方案：外部排序

// 1. 分批加载：把10GB分成10个1GB文件
// 2. 内存内排序：分别对每个文件排序
// 3. 多路归并：用堆排序实现多路归并

public void externalSort(String inputFile, String outputFile) {
    // Step 1: 分成小文件，内存内排序
    splitAndSort(inputFile);
    
    // Step 2: 多路归并
    kWayMerge(outputFile);
}

public void sort(int[] arr) {
    // 问题：给你一个数组，怎么选择排序算法？
    
    // 回答：
    // 1. n <= 50：插入排序
    if (arr.length <= 50) {
        insertionSort(arr);
        return;
    }
    
    // 2. 基本类型（不需要稳定）：快速排序
    // Arrays.sort() 对基本类型就是这么做的
    if (isPrimitiveArray(arr)) {
        quickSort(arr);
        return;
    }
    
    // 3. 对象类型（需要稳定）：TimSort / 归并排序
    // Java 对对象类型就是这么做的
    mergeSort(arr);
}

// 简化版：直接用语言自带的排序
public void sortSimple(int[] arr) {
    Arrays.sort(arr);  // 内部会根据数据特点选择最优算法
}