菜鸟教程 – 学的不仅是技术，更是梦想！

技术网站，更是交流网站

Java

深入浅出Java排序：从基础算法到实战优化

likuolei

深入浅出 Java 排序：从基础算法到实战优化（2026 年实用版）

前言：排序是算法基础中的“常青树”，在 Java 中从面试到项目都高频出现。别担心，我们从 0 基础开始，用生活比喻 + 代码 + 图表一步步讲透。学完这篇，你能手写常见算法、用 Java 内置工具、优化实际场景。基于 Java 17+（兼容旧版），代码全可运行。

我们分成这些模块学（由浅入深）：

  1. 排序基础概念（为什么学？怎么分类？）
  2. 入门级算法（冒泡、选择、插入）
  3. 中级算法（希尔、堆排序）
  4. 高级算法（快速、归并）
  5. Java 内置排序神器（Arrays/Collections + 比较器）
  6. 实战优化技巧（复杂度分析 + 场景选择 + 多线程/并行）
  7. 常见面试题 + 小练习
  8. 总结 & 进阶资源

1. 排序基础概念（先搞懂这些，再看算法不迷糊）

  • 排序是什么？：把乱序数组/列表变成有序（升序/降序）。
  • 为什么学？：数据库查询、搜索、数据处理都靠它。Java 项目中，排序优化能提速 10–100 倍。
  • 分类（超级重要对比表）：
分类方式例子说明
稳定性稳定：冒泡、插入、归并
不稳定：选择、快速、堆		相等元素相对位置不变（稳定好于不稳定，如按成绩排序时保持姓名顺序）
时间复杂度O(n^2)：冒泡、选择、插入
O(n log n)：快速、归并、堆		平均/最坏情况（n=数据量）
空间复杂度O(1)：冒泡、插入
O(n)：归并		原地排序（O(1) 好）
比较 vs 非比较比较：大部分
非比较：桶、计数、基数		非比较更快，但有限制（如整数范围）
  • 生活比喻：排序像整理书架（冒泡：从头比到尾；快速：分堆再排）。

核心记忆：时间 O(n log n) 是主流，空间 O(1) 是优化目标。

2. 入门级算法（O(n^2) 级，简单但慢，适合小数据 n<1000）

2.1 冒泡排序（Bubble Sort）

思路：像气泡浮起，两两比较，大的往后冒。一趟冒一个最大。

代码（升序）：

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {  // n-1 趟
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;  // 优化：已有序早停
    }
}

复杂度：时间 O(n^2) 最坏/平均，O(n) 最好；空间 O(1)；稳定。

优缺点：简单，但慢。实际少用。

2.2 选择排序（Selection Sort）

思路：每趟选最小放前面。

代码：

public static void selectionSort(int[] arr) {
    int n = arr.length;
    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;
        }
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

复杂度：时间 O(n^2) 始终；空间 O(1)；不稳定。

比喻：选班长，一轮一轮挑最矮的站队头。

2.3 插入排序（Insertion Sort）

思路：像打扑克，拿一张插到有序牌堆里。

代码：

public static void insertionSort(int[] arr) {
    int n = arr.length;
    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;
    }
}

复杂度：时间 O(n^2) 最坏，O(n) 最好（近有序）；空间 O(1)；稳定。

优势：对近有序数据超快（自适应）。

3. 中级算法（过渡到高级）

3.1 希尔排序（Shell Sort，插入的升级）

思路：分组插入（gap 递减），从大步到小步。

代码：

public static void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

复杂度：时间 O(n^{1.3–2}) 平均；空间 O(1)；不稳定。

为什么用：比 O(n^2) 快，代码简单。

3.2 堆排序（Heap Sort）

思路：建最大堆，堆顶最大，交换到末尾，再调整。

代码（简版）：

public static void heapSort(int[] arr) {
    int n = arr.length;
    // 建堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 排序
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

复杂度：时间 O(n log n) 始终；空间 O(1)；不稳定。

场景：优先队列基础，Java PriorityQueue 底层类似。

4. 高级算法（O(n log n) 级，项目主力）

4.1 快速排序（Quick Sort）

思路：分治，选 pivot，分左右，再递归。

代码（双指针版）：

public static void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int pivot = partition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];  // 选末尾
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

调用：quickSort(arr, 0, arr.length - 1);

复杂度：时间 O(n log n) 平均，O(n^2) 最坏（优化用随机 pivot）；空间 O(log n) 递归栈；不稳定。

优化：小数组切插入排序，随机 pivot。

4.2 归并排序（Merge Sort）

思路：分治，递归分半，合并有序子数组。

代码：

public static void mergeSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int mid = low + (high - low) / 2;
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    merge(arr, low, mid, high);
}

private static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= high) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, low, temp.length);
}

调用同上。

复杂度：时间 O(n log n) 始终；空间 O(n)；稳定。

优势：稳定，适合链表/外部排序。

5. Java 内置排序神器（99% 项目用这个，别手写）

  • Arrays.sort()：数组排序，底层 TimSort（归并 + 插入混合），O(n log n)，稳定。
int[] arr = {5, 3, 8, 1};
Arrays.sort(arr);  // {1,3,5,8}
  • Collections.sort()：List 排序，同上。
List<Integer> list = Arrays.asList(5, 3, 8, 1);
Collections.sort(list);
  • 自定义比较：用 Comparator（Lambda 写法）。
// 按长度降序排序字符串
List<String> strs = Arrays.asList("apple", "banana", "kiwi");
strs.sort((a, b) -> b.length() - a.length());  // banana, apple, kiwi
  • 对象排序：实现 Comparable 或用 Comparator。
class Person implements Comparable<Person> {
    String name;
    int age;
    public Person(String name, int age) { this.name = name; this.age = age; }

    @Override
    public int compareTo(Person other) {
        return this.age - other.age;  // 按年龄升序
    }
}

List<Person> people = new ArrayList<>();
// 添加对象...
Collections.sort(people);  // 自动用 compareTo

Tips：Java 8+ 用 Stream 排序更优雅：list.stream().sorted(Comparator.comparingInt(p -> p.age)).collect(Collectors.toList());

6. 实战优化技巧（从 O(n^2) 到生产级）

6.1 复杂度分析 & 选择

场景推荐算法/方法为什么？
小数据 (n<100)插入/冒泡简单，近有序快
大数据Arrays.sort / 快速/归并O(n log n)
需要稳定归并 / TimSort保持相等元素顺序
内存紧堆 / 快速 (O(1)/O(log n))原地排序
外部大文件归并（分块读写）空间 O(n) 但可分块
多线程ParallelSort (Java 8+)Arrays.parallelSort(arr); 多核加速

6.2 优化点

  • 避免 O(n^2)：n>10k 必用 O(n log n)。
  • 并行排序：大数组用 Arrays.parallelSort()，利用多核（Fork-Join 框架）。
  • 自定义优化：结合业务，如数据近有序用插入；整数范围小用计数排序（O(n+k)）。
  • 性能测试：用 System.nanoTime() 测时间。

示例：计数排序（非比较，适合小范围整数）。

public static void countSort(int[] arr, int maxVal) {
    int[] count = new int[maxVal + 1];
    for (int num : arr) count[num]++;
    int idx = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i]-- > 0) arr[idx++] = i;
    }
}

6.3 实战案例：排序学生成绩（List）

用 Comparator 链：先按成绩降序，同分按姓名升序。

people.sort(Comparator.comparingInt((Person p) -> -p.score)  // 降序
    .thenComparing(p -> p.name));  // 链式

7. 常见面试题 + 小练习

面试题：

  • 快速排序最坏情况？（有序数组，pivot 选边 → O(n^2)；优化：随机/中位数 pivot）
  • 归并 vs 快速？（归并稳定、空间大；快速快、不稳定）
  • TimSort 是什么？（Java 默认，归并 + 插入 + 二分查找优化）
  • 手写冒泡/快速（必考）

小练习：

  1. 手写插入排序，测试 {5,2,4,6,1,3}。
  2. 用 Arrays.sort 排序 List 按长度升序。
  3. 实现计数排序处理负数（偏移）。

答案自测：练习 1 结果 {1,2,3,4,5,6}。

8. 总结 & 进阶资源

核心 takeaway：

  • 基础：懂 O(n^2) vs O(n log n)，稳定 vs 不稳定。
  • 实战：优先 Java 内置 + Comparator。
  • 优化：根据数据规模/类型选算法，多用 parallel。

进阶：

  • LeetCode：Sort an Array (912)，Merge Intervals (56)。
  • 书：《算法导论》排序章。
  • Java 源码：看 Arrays.java 的 TimSort 实现。

你现在想深入哪部分？

  • 更多代码示例（e.g., 基数排序）？
  • 面试手撕题解析？
  • Java 并发排序实战？
  • 还是对比 Python/JavaScript 排序？

告诉我，继续陪你优化～ 😊

网站 http://yingjuxia.com
文章已创建 4323

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

相关文章

开始在上面输入您的搜索词，然后按回车进行搜索。按ESC取消。

返回顶部