跳至主要內容

十大排序算法详解

老张2026/4/18大约 14 分钟算法排序快排归并排序堆排序

十大排序算法详解

排序算法是面试中最基础、考频最高的模块之一。本文用可交互动画组件帮你真正搞懂每种排序的执行过程，而不只是背模板代码。

算法总览对比表

算法平均时间最坏时间空间复杂度稳定性适用场景
冒泡排序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(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)不稳定TopK 问题
计数排序O(n+k)O(n+k)O(k)稳定整数范围小
桶排序O(n+k)O(n²)O(n+k)稳定均匀分布浮点数
基数排序O(n×k)O(n×k)O(n+k)稳定多关键字排序

1. 冒泡排序

核心思想：相邻元素两两比较，大的"冒泡"到右边。每轮结束后，最大元素落到末尾。

稳定性分析：相等元素不交换，稳定。

执行过程可视化

以数组 [64, 34, 25, 12, 22] 为例，完整展示前两轮冒泡过程：

第1轮：比较 arr[0]=64 和 arr[1]=34，64 > 34，交换
64
0
34
1
25
2
12
3
22
4
1 / 10
比较中 pivot基准 已排序 未处理

Java 实现

public 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 tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break; // 优化：本轮无交换则已有序
    }
}

2. 选择排序

核心思想：每轮从未排序区间中找到最小值，放到已排序区间末尾。

稳定性分析：交换操作可能破坏相等元素的相对顺序，不稳定。

执行过程可视化

以数组 [64, 25, 12, 22, 11] 为例，红色标注当前轮次找到的最小值：

第1轮：从全数组中扫描，寻找最小值，当前 minIdx=0 (64)
64
0
25
1
12
2
22
3
11
4
1 / 10
比较中 pivot基准 已排序 未处理

Java 实现

public 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;
        }
        int tmp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = tmp;
    }
}

3. 插入排序

核心思想：将未排序元素逐个插入到已排序区间的正确位置，类似整理扑克牌。

稳定性分析：遇到相等元素停止移动，稳定。对近似有序数组效率极高，时间复杂度接近 O(n)。

执行过程可视化

以数组 [5, 3, 8, 1, 9] 为例，绿色为已排序区间，橙色为当前待插入元素：

取 arr[1]=3 准备插入已排序区 [5]
5
0
3
1
8
2
1
3
9
4
1 / 8
比较中 pivot基准 已排序 未处理

Java 实现

public 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;
    }
}

4. 希尔排序

核心思想：插入排序的改进版，先按较大间隔分组做插入排序，逐步缩小间隔至1，使数组"接近有序"后效率极高。

间隔可视化

以 [8, 3, 7, 1, 6, 2, 9, 4] 为例，初始间隔 gap=4：

gap=4 分组
组1：
8
6
组2：
3
2
组3：
7
9
组4：
1
4

各组分别做插入排序后：[6, 2, 7, 1, 8, 3, 9, 4]

Java 实现

public 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 temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

5. 快速排序（重点）

核心思想：选取 pivot，通过 partition 将数组分为两部分（左边 <= pivot，右边 >= pivot），递归排序两部分。

面试中手写快排是高频考点，必须掌握 partition 的双指针写法！

Partition 过程可视化

以 [3, 6, 8, 10, 1, 2, 1]，以最后元素 arr[6]=1 为 pivot 的完整 partition 过程（紫色=pivot，黄色=当前比较元素）：

初始：选取 arr[6]=1 为 pivot（紫色），i=-1，j 从左向右扫描
3
0
6
1
8
2
10
3
1
4
2
5
1
6
1 / 9
比较中 pivot基准 已排序 未处理

递归树（Mermaid）

Java 实现

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIdx = partition(arr, low, high);
        quickSort(arr, low, pivotIdx - 1);
        quickSort(arr, pivotIdx + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        // 右指针左移，找到小于pivot的元素
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        // 左指针右移，找到大于pivot的元素
        while (low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot; // pivot就位
    return low;
}

优化技巧：随机选取 pivot 可避免最坏情况（已排序数组）；数组长度 <= 10 时切换为插入排序。

6. 归并排序（重点）

核心思想：分治法，将数组不断二分直到长度为1，再两两合并为有序数组。

稳定性：合并时遇到相等元素优先取左边，稳定。唯一能稳定排序链表的 O(n log n) 算法。

分治过程（Mermaid）

合并过程可视化

合并有序数组 [1, 3, 5] 和 [2, 4, 6]，用 L/R 指针标注当前比较位置，已归并元素置绿色：

初始：L指针指向左数组头 arr[0]=1，R指针指向右数组头 arr[4]=2
1 L
3
5
|
2 R
4
6
1 / 7

Java 实现

public 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 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) {
        // 稳定性关键：相等时优先取左边
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid)  temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
}

7. 堆排序

核心思想：建立最大堆，然后反复将堆顶（最大值）与末尾元素交换，堆大小减1，再重新堆化。

堆化过程（Mermaid）

以 [4, 10, 3, 5, 1] 建立最大堆：

Java 实现

public 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 tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        heapify(arr, i, 0);
    }
}

private 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 tmp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = tmp;
        heapify(arr, n, largest);
    }
}

8. 计数 / 桶 / 基数排序

计数排序

适用：非负整数，且值域范围 k 不大时。

public void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    for (int x : arr) count[x]++;
    int idx = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i]-- > 0) arr[idx++] = i;
    }
}

桶排序

适用：均匀分布的浮点数，将数据分散到若干个"桶"中，各桶内独立排序再合并。

public void bucketSort(double[] arr) {
    int n = arr.length;
    List<List<Double>> buckets = new ArrayList<>();
    for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
    for (double x : arr) {
        int idx = (int)(x * n); // 映射到桶
        buckets.get(idx).add(x);
    }
    int k = 0;
    for (List<Double> b : buckets) {
        Collections.sort(b);
        for (double x : b) arr[k++] = x;
    }
}

基数排序

适用：整数，按个位、十位、百位分别做计数排序。

public void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countByDigit(arr, exp);
    }
}

private void countByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];
    for (int x : arr) count[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[--count[(arr[i] / exp) % 10]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, n);
}

面试要点速记

快速排序 vs 归并排序

  • 快排：原地排序，空间 O(log n)，不稳定，平均最快，但最坏 O(n²)
  • 归并：需要 O(n) 额外空间，稳定，时间严格 O(n log n)，适合链表和外排序
  • Java 的 Arrays.sort(int[]) 用的是双轴快排，Arrays.sort(Object[]) 用的是TimSort（归并改进）

堆排序的使用场景

堆排序虽然时间复杂度优秀，但由于缓存命中率低（跳跃式访问内存），实际速度常慢于快排。主要用于TopK 问题（维护一个大小为 K 的堆）而非整体排序。

编辑此页
最近更新:
贡献者: xiaozhangge