Java排序算法案例有哪些

Java排序算法实战案例全解析：从基础到企业级应用

---

📚 目录导读（Table of Contents）

1. 开篇问答：为什么排序算法是Java面试的"试金石"？
2. Java内置排序：Arrays.sort()与Collections.sort()的底层秘密
3. 手写经典排序案例
   • 1 快速排序（Quick Sort）——分治思想的极致
   • 2 归并排序（Merge Sort）——稳定性的王者
   • 3 堆排序（Heap Sort）——优先队列的基石
4. 实战案例：海量数据Top-K问题（基于堆排序）
5. 实战案例：对象多字段排序（Comparator链式写法）
6. 性能对比与选型指南（含JMH基准测试）
7. 高频面试问答：排序算法变形题与陷阱

---

开篇问答：为什么排序算法是Java面试的"试金石"？

Q： 市面上有现成的Arrays.sort()，为什么还要手写排序？
A： 这是区分"API调用者"与"算法工程师"的关键，面试官考察的是：

• 是否理解时间/空间复杂度的权衡（如快排的平均O(n log n) vs 最坏O(n²)）
• 是否掌握稳定性（归并稳定，快排不稳定，对对象排序影响巨大）
• 能否应对定制化场景（如内存受限时用外排,实时数据用插入排序的优化版TimSort）

---

Java内置排序：Arrays.sort()与Collections.sort()的底层秘密

案例代码：

int[] arr = {5, 2, 9, 1};
Arrays.sort(arr); // 对基本类型使用Dual-Pivot QuickSort（双轴快排）
List<String> list = Arrays.asList("banana", "apple");
Collections.sort(list); // 对对象类型使用TimSort（归并+插入的混合优化）

深度解析：

• 基本类型（int, char等）使用双轴快排（Dual-Pivot QuickSort），其性能比传统快排快10%-20%。
• 对象类型使用TimSort，它利用了数据中已有序片段（run），在近乎有序数据上接近O(n)复杂度，这也是Java对Comparable设计哲学的体现——稳定性对对象排序至关重要（如先按姓名排，再按年龄排）。
• 陷阱：Arrays.parallelSort()（并行排序）仅当数据量 > 8192时启用，且需要可用CPU核心数>1,否则退化。

---

手写经典排序案例

1 快速排序（Quick Sort）——分治思想的极致

案例：单轴快排 + 荷兰国旗优化（处理重复元素）

public static void quickSort(int[] arr, int L, int R) {
    if (L < R) {
        // 随机选基准，避免最坏O(n²)
        swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
        int[] p = partition(arr, L, R); // 返回等于区域边界 [less+1, more-1]
        quickSort(arr, L, p[0] - 1);
        quickSort(arr, p[1] + 1, R);
    }
}
private static int[] partition(int[] arr, int L, int R) {
    int less = L - 1, more = R;
    while (L < more) {
        if (arr[L] < arr[R]) swap(arr, ++less, L++);
        else if (arr[L] > arr[R]) swap(arr, --more, L);
        else L++;
    }
    swap(arr, more, R);
    return new int[]{less + 1, more}; // 等于区域左右边界
}

特点：最坏O(n²)（每次基准都是极值），但通过随机化几乎不可能触发；空间复杂度递归栈O(log n)。

2 归并排序（Merge Sort）——稳定性的王者

案例：合并两个有序数组（处理逆序对数量）

public static int mergeSort(int[] arr, int l, int r) {
    if (l == r) return 0;
    int mid = l + ((r - l) >> 1);
    return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
private static int merge(int[] arr, int l, int mid, int r) {
    int[] help = new int[r - l + 1];
    int i = 0, p1 = l, p2 = mid + 1, res = 0;
    while (p1 <= mid && p2 <= r) {
        // 左边小于等于右边时，先拷贝左边，并累加右边剩余数量为逆序对
        res += arr[p1] <= arr[p2] ? (r - p2 + 1) : 0;
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) help[i++] = arr[p1++];
    while (p2 <= r) help[i++] = arr[p2++];
    System.arraycopy(help, 0, arr, l, help.length);
    return res;
}

应用：求逆序对数量（LeetCode 493）是归并排序的经典变形题，体现了"分治+合并时统计"的思维。

3 堆排序（Heap Sort）——优先队列的基石

案例：利用大根堆求每次最大值（堆化过程）

public static void heapSort(int[] arr) {
    // ① 从最后一个非叶子节点往前，构建大根堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
    // ② 依次把堆顶（最大值）交换到末尾，缩小范围重新堆化
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, 0, i);
    }
}
private static void heapify(int[] arr, int idx, int size) {
    int left = idx * 2 + 1;
    while (left < size) {
        int largest = (left + 1 < size) && arr[left + 1] > arr[left] ? left + 1 : left;
        largest = arr[largest] > arr[idx] ? largest : idx;
        if (largest == idx) break;
        swap(arr, largest, idx);
        idx = largest;
        left = idx * 2 + 1;
    }
}

注意：堆排序时间复杂度稳定O(n log n)，但其不稳定，且常数因子比快排大，平常使用较少，但在优先级队列（PriorityQueue）中是不可或缺的。

---

实战案例：海量数据Top-K问题（基于堆排序）

场景：从10亿个整数中找出最大的100个数。
思路：维护一个大小为K的小根堆（堆顶最小），遍历数据时，如果当前元素大于堆顶，则替换堆顶并重新堆化。
代码实现：

public List<Integer> topK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        if (minHeap.size() < k) {
            minHeap.offer(num);
        } else if (num > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(num);
        }
    }
    return new ArrayList<>(minHeap);
}

复杂度：时间复杂度O(n log K)，空间复杂度O(K)，当K远小于n时，优于全局排序（O(n log n)）。
延伸：如果要求精确Top-K且允许误差，可用Timsort分块预处理或布隆过滤器优化,但那是另一个话题了。

---

实战案例：对象多字段排序（Comparator链式写法）

场景：对员工对象按薪资降序、年龄升序、工号升序排序。
Java 8+ Stream API写法：

List<Employee> employees = ...;
employees.sort(Comparator
    .comparing(Employee::getSalary).reversed()
    .thenComparing(Employee::getAge)
    .thenComparingInt(Employee::getId));

底层原理：Comparator链式调用会生成一个复合Comparator，内部使用compare()方法按顺序比较各字段，若前一个字段相等才进入下一个，这本质上利用了归并排序的稳定性——即对第一关键字排序后,后续排序不会破坏前序顺序。

避坑指南：

• 陷阱1：.reversed()只作用于紧邻的前一个比较器，而不是整个链，正确写法是.comparing(...).reversed().thenComparing(...)。
• 陷阱2：对基本类型避免自动装箱，使用thenComparingInt、thenComparingDouble等专用方法。

---

性能对比与选型指南（含JMH基准测试）

排序算法	时间复杂度（平均/最坏）	空间复杂度	稳定性	适用场景
双轴快排（内置）	O(n log n) / O(n²)	O(log n)	不稳定	基本类型数组，数据量中等
TimSort（内置）	O(n log n) / O(n)	O(n)	稳定	对象数组/链表，部分有序
快速排序	O(n log n) / O(n²)	O(log n)	不稳定	内存足够，没有稳定性要求
归并排序	O(n log n)	O(n)	稳定	需要稳定性，或求逆序对
堆排序	O(n log n)	O(1)	不稳定	内存受限，Top-K问题

JMH基准测试案例（仅骨架）：

@Benchmark
@BenchmarkMode(Mode.AverageTime)
public void testQuickSort() {
    Arrays.sort(copyArray); // 内置快排
}

经验之谈：

• 数据量小（<100）时，插入排序反而最快（常数因子小），TimSort在底层就利用了这一点。
• 数据近乎有序时，TimSort几乎O(n)，而快排仍会退化。
• 需要稳定时，绝不用快排；需要内存极少时,用堆排序。

---

高频面试问答：排序算法变形题与陷阱

Q1： 对包含100万个字符串的数组排序，如何保证内存占用最小？
A： 不要用归并（需要额外N空间），用三向切分快排（快速排序变种，专门处理大量重复元素），空间O(log n)，如果字符串是英文，可考虑基数排序（LSD），空间O(N+K),但需自定义字符桶。

Q2： 自定义对象实现了Comparable，但sort结果不是预期的稳定排序，为什么？
A： 因为Arrays.sort(Object[])在JDK 8以后使用TimSort，它是稳定排序；但你若用了parallelSort()，当数据量大时可能使用并行合并，稳定性与JDK版本相关，建议显式传入Comparator并保证字段比较逻辑不冲突。

Q3： 如何判断一个数组是否已排好序？最快算法是什么？
A： 线性扫描比较相邻元素即可O(n)，不要尝试排序再比较（O(n log n)），这是常见的陷阱题。

Q4： 十大排序算法中，哪个能同时做到最优时间复杂度、稳定、原地排序？
A： 不存在，数学证明：基于比较的排序，最坏下界是O(n log n)；且稳定与原地（空间O(1)）不可兼得（除非用复杂的原地归并，但常数极大），实际工程中放弃稳定性换取性能，或用额外空间换稳定。

Q5： 在Java中，Collections.sort(List)和list.sort(Comparator)有区别吗？
A： 无本质区别，前者是Java 8之前的历史方法，内部委托给list.sort，但注意list.sort是List接口的默认方法，直接对集合内部数组排序，而Collections.sort还支持CopyOnWriteArrayList等特殊集合的重写。

---

排序算法不仅是面试的敲门砖，更是理解数据结构与算法权衡思维的钥匙，从内置API的底层优化到手写实现，再到海量数据的工程实践，每一个案例都在提醒我们：“最优”永远是相对的，取决于数据规模、稳定性需求与内存约束，建议读者在IDE中分别运行上述代码，观察不同数据分布（随机、有序、大量重复）下的耗时差异,这会比死记硬背复杂度公式更有价值。