Java 经典排序算法六件套：从冒泡到堆排，一次彻底搞懂

面试官让你手写排序？稳住，看完这一篇就上岸了

引言

排序算法是程序员的基本功，也是面试的”硬通货”——大厂校招笔试几乎必考，现场手写快排、归并、堆排更是家常便饭。

网上讲排序的文章多如牛毛，但大多停留在”翻译课本”层面：列定义、贴代码、说复杂度，看完你还是不会用、不会选、不会变形。

这篇文章不一样。我用 6 个核心算法 × 5 个固定板块（核心思想 → 代码实现 → 关键细节 → 适用场景 → 面试变形）的统一结构，把每种排序讲透。每段代码都经过实测，每个细节都是面试高频坑，每个变形都是大厂真题改编。

读完这一篇，你能做到的：

• 6 种排序闭着眼睛都能手写
• 知道每种排序的”最佳战场”和”绝对禁区”
• 面对排序变形题（比如 TopK、第 k 大）有清晰的思路模板

---

1. 冒泡排序：最简单的排序，没有之一

面试官让手写排序？掏出冒泡，至少能及格

核心思想

• 从头到尾依次比较相邻两个元素
• 如果前面比后面大，就交换（大的往后”冒”）
• 每一趟结束后，最大的元素沉到了最后
• 重复以上过程，每趟少比较一个（最后已有序）

优化点：如果某趟一次都没交换，说明数组已经有序——立即终止，这就是最好情况 O(n) 的来源。

复杂度：最坏 O(n²) / 最好 O(n) / 平均 O(n²)

Java 实现

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; 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;
        }
    }
}

三个关键细节

• 外层循环 i < n - 1，不是 i < n——n 个元素排好 n-1 个
• 内层循环 j < n - 1 - i，减 i 是关键（末尾已有序）
• swapped 标志必须有——O(n²) 变 O(n) 的唯一机会

适用场景

• 适用：数据量极小（< 100）/ 基本有序 / 教学演示
• 不适用：大数据量 / 生产环境

面试变形

• 鸡尾酒排序（双向冒泡）：从左到右冒大，从右到左冒小
• 奇偶排序：奇数位和偶数位分别比较，适合并行
• 冒泡第 k 大：只跑 k 趟冒泡

---

2. 选择排序：最简单粗暴的”找最小”

每一轮都挑最矮的站前面——像极了军训排队

核心思想

• 从位置 i 开始，扫描 i 到末尾所有元素
• 找到最小元素的下标 minIndex
• 把 arr[i] 和 arr[minIndex] 交换
• i++，重复直到末尾

每轮只交换一次（比冒泡交换次数少），但比较次数不变。

复杂度：最好/最坏/平均 O(n²)。原地排序，不稳定。

Java 实现

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

两个关键细节

• 外层 i < n - 1
• **minIndex = i**，不能写成 minIndex = 0

适用场景

• 适用：数据量极小 / 交换成本极高 / 无稳定性要求
• 不适用：> 100 数据量 / 要求稳定

面试变形

• 双向选择排序：每轮同时找最大和最小
• 选择第 k 小：只跑 k 轮

---

3. 插入排序：抓牌怎么排，它就怎么排

打麻将抓牌时你怎么理牌？插入排序就是那么干的

核心思想

• 从第 1 个元素开始（第 0 个视为已排序）
• 取出当前元素 key
• 从 i - 1 往前扫描，把比 key 大的元素统统往后挪
• 找到合适位置，插入 key
• 重复直到最后一个元素

关键：搬移元素比交换更高效。

复杂度：最好 O(n) / 最坏 O(n²) / 平均 O(n²)。稳定排序。

Java 实现

public class InsertionSort {
    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;
        }
    }
}

三个关键细节

• i 从 1 开始
• **while (j >= 0 && arr[j] > key)**——用 > 保证稳定性
• 用 key 保存当前值——搬移过程中 arr[i] 会被覆盖

适用场景

• 适用：数据量小 / 数据基本有序 / 数据流式插入
• 不适用：大数据量乱序 / 链表
• 现实应用：JDK Arrays.sort() 对 < 47 个元素的小数组用插入排序；快排递归到小数组也切到插入排序

面试变形

• 二分插入排序：用二分查找找插入位置
• 希尔排序：分组插入排序，先粗排再细排
• 链表插入排序：改指针而不是搬移

---

4. 快速排序：分治思想的最强代表

面试官让你手写快排？稳住，写完就上岸了

核心思想

• 从数组中选一个元素作为基准（pivot）
• 分区（partition）：把小于 pivot 的放左边，大于 pivot 的放右边
• 递归对左右两个子数组执行同样的操作
• 直到每个子数组只剩一个元素

复杂度：最好 O(n log n) / 平均 O(n log n) / 最坏 O(n²)。

Java 实现（经典双指针法）

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 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++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
}

四个关键细节

• 分区函数 i 从 low - 1 开始
• for 循环只到 j < high，不包括 pivot
• 递归终止 low < high，不是 low <= high
• 最坏情况避免——随机选 pivot

适用场景

• 适用：数据量大且乱序 / 内存充足 / 要求平均性能高
• 不适用：数据基本有序 / 要求稳定 / 链表
• JDK 实现：Arrays.sort() 用 Dual-Pivot QuickSort；小数组切插入排序；递归过深切堆排序

面试变形

• 随机快排：pivot 随机选
• 三路快排：< pivot / = pivot / > pivot 三块
• 第 k 大元素（快速选择）：只递归一边，平均 O(n)
• 双基准快排：两个 pivot 分三块

---

5. 归并排序：稳定排序的”秩序守护者”

分而治之的典范——拆到最小，再有序合并

核心思想

• 递归拆分：把数组从中间一分为二，直到每个子数组只剩一个元素
• 归并合并：两个有序子数组合并成一个有序数组
• 关键操作：比较两个子数组的头部，把小的放入临时数组

复杂度：稳定 O(n log n)。空间复杂度：O(n)。稳定排序。

Java 实现

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

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        for (i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
    }
}

三个关键细节

• 递归终止 left >= right
• mid = left + (right - left) / 2 防溢出
• merge 里 <= 保证稳定性

适用场景

• 适用：需要稳定排序 / 链表排序 / 外部排序
• 不适用：内存受限 / 近乎有序的小数组

面试变形

• 自底向上归并：迭代版，适合链表
• 链表归并排序：快慢指针找中点，改指针
• 求逆序对：归并时统计跨左右的有序对数量

---

6. 堆排序：用二叉树思维排序

借优先级队列的壳，排最大最小的序

核心思想

• 建最大堆：从最后一个非叶子节点开始，自底向上执行 siftDown
• 排序：把堆顶（最大值）与末尾交换，堆大小减 1
• 恢复堆：对新的堆顶执行 siftDown，恢复堆性质
• 重复直到堆只剩一个元素

关键：siftDown（下沉）是堆排序的灵魂。

复杂度：建堆 O(n) / 排序 O(n log n) / 总体 O(n log n)。原地排序，不稳定。

Java 实现

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            siftDown(arr, i, 0);
        }
    }

    private static void siftDown(int[] arr, int heapSize, int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        if (left < heapSize && arr[left] > arr[largest]) largest = left;
        if (right < heapSize && arr[right] > arr[largest]) largest = right;
        if (largest != index) {
            swap(arr, index, largest);
            siftDown(arr, heapSize, largest);
        }
    }
}

三个关键细节

• 建堆从 n/2 - 1 开始，不是 n-1
• siftDown 里 arr[left] > arr[largest]——要排升序必须用最大堆
• heapSize 在排序中递减

适用场景

• 适用：需要 O(1) 空间的 O(n log n) / 优先级队列底层 / TopK 问题
• 不适用：要求稳定 / 数据基本有序 / 小数据量

面试变形

• 最小堆排序：建最小堆，排出来是降序
• TopK：维护大小为 K 的小顶堆
• 堆化数组：siftDown 是核心，siftUp 用于插入

---

7. 六种排序全景对比

算法	平均时间	最坏时间	空间	稳定性	一句话精髓
冒泡	O(n²)	O(n²)	O(1)	稳定	大数往后冒
选择	O(n²)	O(n²)	O(1)	不稳	每轮挑最小
插入	O(n²)	O(n²)	O(1)	稳定	抓牌理牌
快排	O(n log n)	O(n²)	O(log n)	不稳	分治分区
归并	O(n log n)	O(n log n)	O(n)	稳定	拆了再合
堆排	O(n log n)	O(n log n)	O(1)	不稳	堆顶沉底

面试优先级

快排 > 归并 > 堆排 > 插入 > 冒泡 ≈ 选择

面试官让你手写排序，快排是 80% 的首选答案。归并次之，重点考稳定排序和链表场景。堆排一般不会让你从头写，更多是问 TopK 问题时顺带考察。

---

总结与行动建议

核心观点

• 简单排序（冒泡/选择/插入）：O(n²) 但代码简单，适合小数据量和教学场景
• 分治排序（快排/归并）：O(n log n) 是工业界主力，快排追求速度、归并追求稳定
• 堆排序：O(1) 空间的 O(n log n)，TopK 问题的最优解

三个关键洞察

1. “稳定”是个硬需求——如果面试官要求稳定排序，冒泡/插入/归并是唯一选择
2. “原地”和”时间”是 trade-off——堆排牺牲稳定性换 O(1) 空间，归并牺牲空间换稳定性
3. JDK 不会用 O(n²) 排序——Arrays.sort() 底层是快排+归并+插入的混合体

行动建议

1. 打开 LeetCode，把 912. 排序数组 用这 6 种方法各写一遍
2. 专项突破：215. 数组中的第 K 个最大元素（快排变形） + 347. 前 K 个高频元素（堆排变形）
3. 链表专项：148. 排序链表（归并变形）—— 考你快慢指针 + 归并的结合
4. 进阶题：剑指 Offer 51. 数组中的逆序对（归并 + 计数）

写完了这 6 套，你就不再惧怕任何排序题。

---