排序算法 | 小菜鸟

排序算法全解析：从原理到应用

排序是数据处理中的基础操作，根据数据是否全部在内存中，分为内排序（全在内存）和外排序（需内外存交换）。内排序是日常开发的重点，按策略可分为插入排序、交换排序、选择排序、归并排序等。本文详细解析各类内排序算法的原理、实现、性能及适用场景。

排序算法基础概念

内排序与外排序

内排序：待排序数据全部在内存中，无需磁盘 IO，如插入排序、快速排序等。
外排序：数据量超过内存容量，需分批加载到内存排序，再合并结果（如归并排序的外部实现）。

关键评价指标

时间复杂度：算法执行时间随数据规模n的增长趋势（关注最坏、平均、最好情况）。
空间复杂度：算法所需额外存储空间（如归并排序需 O (n) 辅助空间）。
稳定性：排序后，相等元素的相对顺序是否保持不变（如[2, 2*]排序后仍为[2, 2*]则稳定）。

插入排序：逐步构建有序序列

插入排序的核心思想：将待排序元素逐个插入到已排序部分的正确位置，使已排序部分始终有序。

1. 直接插入排序

基本思想

将数组分为 “已排序区” 和 “未排序区”，初始已排序区只有第一个元素。
从第二个元素开始，依次将未排序区的元素插入到已排序区的合适位置（比它大的元素后移）。

示例步骤（以`[67, 67, 14, 52, 29, 9, 90, 54, 87, 71]`为例）：

初始：[67]（已排序），[67, 14, 52, 29, 9, 90, 54, 87, 71]（未排序）。
插入 67：已排序区变为[67, 67]。
插入 14：14 < 67，67 和 67 后移，已排序区变为[14, 67, 67]。
依次插入剩余元素，最终得到有序数组。

代码实现

int[] arr = {67, 67, 14, 52, 29, 9, 90, 54, 87, 71};
for (int i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i-1]) { // 当前元素需插入已排序区
        int temp = arr[i];
        int j = i-1;
        // 比temp大的元素后移
        while (j >= 0 && arr[j] > temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp; // 插入正确位置
    }
}

性能分析

时间复杂度：
- 最好：O (n)（已排序数组，无需移动元素）。
- 最坏 / 平均：O (n²)（逆序数组，每次插入需移动所有已排序元素）。
空间复杂度：O (1)（仅需常量空间）。
稳定性：稳定（相等元素不交换，相对顺序不变）。

适用场景

小规模数据或部分有序数组（如接近排序的日志数据）。

2. 希尔排序（缩小增量排序）

基本思想

对直接插入排序的优化：按 “步长” 将数组分组，每组内进行直接插入排序；逐步减小步长（如n/2, n/4, ..., 1），最终步长为 1 时完成排序。
目的：通过分组排序，让元素快速 “跳” 到接近最终位置，减少后续移动次数。

示例步骤（步长初始为 5）：

步长 5：数组分为 5 组[67,9], [67,90], [14,54], [52,87], [29,71]，每组内排序后为[9,67], [67,90], [14,54], [52,87], [29,71]，数组变为[9,67,14,52,29,67,90,54,87,71]。
步长 2：分为 2 组[9,14,29,90,87], [67,52,67,54,71]，每组排序后数组变为[9,52,14,54,29,67,87,67,90,71]。
步长 1：退化为直接插入排序，最终得到有序数组。

代码实现

int[] arr = {67, 67, 14, 52, 29, 9, 90, 54, 87, 71};
int gap = arr.length / 2; // 初始步长
while (gap >= 1) {
    for (int i = gap; i < arr.length; i++) {
        if (arr[i] < arr[i-gap]) { // 组内元素需插入
            int temp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > temp) {
                arr[j+gap] = arr[j];
                j -= gap;
            }
            arr[j+gap] = temp;
        }
    }
    gap /= 2; // 减小步长
}

性能分析

时间复杂度：取决于步长选择，平均约 O (n¹・³)，最坏 O (n²)。
空间复杂度：O(1)。
稳定性：不稳定（分组排序可能破坏相等元素的相对顺序）。

适用场景

中大规模乱序数组（比直接插入排序效率高）。

交换排序：通过交换纠正逆序

交换排序的核心思想：两两比较元素，若逆序则交换，直至无逆序对。

1. 冒泡排序

基本思想

重复遍历数组，每次比较相邻元素，逆序则交换；每轮遍历后，最大元素 “浮” 到数组末尾（如气泡上升）。
优化：若某轮无交换，说明数组已有序，可提前终止。

示例步骤：

第一轮：比较67&67（不换）、67&14（换）、67&52（换）… 最大元素 90 移到末尾，数组变为[67,14,52,29,9,67,54,87,71,90]。
第二轮：次大元素 87 移到倒数第二位，数组变为[14,52,29,9,67,54,67,71,87,90]。
直至某轮无交换，排序完成。

代码实现

int[] arr = {67, 67, 14, 52, 29, 9, 90, 54, 87, 71};
for (int i = 0; i < arr.length-1; i++) {
    boolean swapped = false; // 标记是否交换
    for (int j = 1; j < arr.length - i; j++) {
        if (arr[j-1] > arr[j]) { // 逆序则交换
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
            swapped = true;
        }
    }
    if (!swapped) break; // 无交换，提前终止
}

性能分析

时间复杂度：
- 最好：O (n)（已排序数组，一轮无交换）。
- 最坏 / 平均：O (n²)。
空间复杂度：O(1)。
稳定性：稳定（相邻交换，相等元素不交换）。

适用场景

小规模数据或教学演示（思路简单，但效率低）。

2. 快速排序

基本思想

分治策略：
1. 选基准：从数组中选一个元素作为基准（如第一个元素）。
2. 分区：将数组分为两部分，左部≤基准，右部≥基准。
3. 递归：对左右两部分重复上述步骤，直至子数组长度为 1。

示例步骤（基准为 67）：

分区：左指针从左找 > 67 的元素（52≤67→右移；29≤67→右移… 找到 90），右指针从右找 < 67 的元素（71≥67→左移；87≥67→左移… 找到 54），交换 90 和 54；继续分区，最终基准 67 移到中间，左部[14,52,29,9,54]，右部[67,90,87,71]。
递归排序左右部，最终得到有序数组。

代码实现

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left]; // 基准
    int i = left, j = right;
    while (i < j) {
        // 右指针找<基准的元素
        while (i < j && arr[j] >= pivot) j--;
        // 左指针找>基准的元素
        while (i < j && arr[i] <= pivot) i++;
        // 交换
        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 基准归位
    arr[left] = arr[i];
    arr[i] = pivot;
    // 递归左右
    quickSort(arr, left, i-1);
    quickSort(arr, i+1, right);
}

性能分析

时间复杂度：
- 最好 / 平均：O (nlogn)（平衡分区，递归深度 logn）。
- 最坏：O (n²)（极端不平衡分区，如已排序数组选第一个为基准）。
空间复杂度：O (logn)（递归栈深度）。
稳定性：不稳定（基准交换可能破坏相等元素顺序）。

适用场景

大规模乱序数组（实际应用中最快的内排序之一，如 Java 的Arrays.sort()对原始类型使用双轴快速排序）。

选择排序：每次选最值放到有序区

选择排序的核心思想：每轮从待排序区选出最值，放到已排序区的末尾，逐步构建有序数组。

1. 直接选择排序

基本思想

初始已排序区为空，待排序区为整个数组。
每轮从待排序区选最小（或最大）元素，与待排序区第一个元素交换，已排序区扩大一位。

示例步骤：

第一轮：待排序区[67,67,14,52,29,9,90,54,87,71]，最小元素为 9，与第一个元素 67 交换，数组变为[9,67,14,52,29,67,90,54,87,71]。
第二轮：待排序区[67,14,52,29,67,90,54,87,71]，最小元素 14，与 67 交换，数组变为[9,14,67,52,29,67,90,54,87,71]。
直至待排序区为空。

代码实现

int[] arr = {67, 67, 14, 52, 29, 9, 90, 54, 87, 71};
for (int i = 0; i < arr.length-1; i++) {
    int minIndex = i; // 记录最小值索引
    for (int j = i+1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    // 交换最小值到当前位置
    if (minIndex != i) {
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

性能分析

时间复杂度：O (n²)（无论有序与否，都需遍历待排序区）。
空间复杂度：O(1)。
稳定性：不稳定（交换非相邻元素，可能破坏相等元素顺序）。

适用场景

数据量小，或对交换次数敏感的场景（每轮最多一次交换）。

2. 堆排序

基本思想

利用堆（完全二叉树）的特性：大顶堆（父节点≥子节点）的堆顶是最大值。
步骤：
1. 构建大顶堆（将数组转为大顶堆）。
2. 堆顶（最大值）与末尾元素交换，最大值固定在末尾。
3. 对剩余元素重新构建大顶堆，重复步骤 2，直至数组有序。

示例步骤：

构建大顶堆：将[67,67,14,52,29,9,90,54,87,71]转为大顶堆，堆顶为 90。
交换 90 与末尾元素 71，数组变为[71,67,14,52,29,9,67,54,87,90]，对前 9 个元素重建大顶堆。
重复交换堆顶与当前末尾元素，最终得到有序数组。

代码实现

public static void heapSort(int[] arr) {
    int n = arr.length;
    // 构建大顶堆（从最后一个非叶子节点开始）
    for (int i = n/2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, n);
    }
    // 堆排序
    for (int i = n-1; i > 0; i--) {
        // 堆顶（最大）与当前末尾交换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 对剩余元素重建大顶堆
        adjustHeap(arr, 0, i);
    }
}

// 调整堆（确保父节点≥子节点）
private static void adjustHeap(int[] arr, int parent, int length) {
    int temp = arr[parent];
    int child = 2*parent + 1; // 左子节点
    while (child < length) {
        // 选左右子节点中较大的
        if (child+1 < length && arr[child] < arr[child+1]) {
            child++;
        }
        if (temp >= arr[child]) break; // 父节点≥子节点，无需调整
        arr[parent] = arr[child]; // 子节点上移
        parent = child;
        child = 2*parent + 1;
    }
    arr[parent] = temp; // 父节点归位
}

性能分析

时间复杂度：O (nlogn)（建堆 O (n)，排序 O (nlogn)）。
空间复杂度：O (1)（原地排序）。
稳定性：不稳定（交换堆顶与末尾元素，可能破坏顺序）。

适用场景

大规模数据，对空间敏感（原地排序），如内存有限的嵌入式系统。

归并排序：分而治之的合并策略

基本思想

分治策略：
1. 分：将数组递归分为两个等长子数组，直至子数组长度为 1。
2. 治：将两个有序子数组合并为一个有序数组。

示例步骤：

分：[67,67,14,52,29,9,90,54,87,71]→[67,67,14,52,29]和[9,90,54,87,71]→继续分至子数组长度为 1。
合：将[67]与[67]合并为[67,67]；[14]与[52]合并为[14,52]… 最终合并为完整有序数组。

代码实现

static int[] temp; // 辅助数组

public static void mergeSort(int[] arr) {
    temp = new int[arr.length];
    sort(arr, 0, arr.length-1);
}

private static void sort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    sort(arr, left, mid); // 左半排序
    sort(arr, mid+1, right); // 右半排序
    merge(arr, left, mid, right); // 合并
}

private static void merge(int[] arr, int left, int mid, int right) {
    int i = left, j = mid+1, k = left;
    // 合并两个有序子数组
    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++];
    // 复制回原数组
    System.arraycopy(temp, left, arr, left, right-left+1);
}

性能分析

时间复杂度：O (nlogn)（分治深度 logn，每层合并 O (n)）。
空间复杂度：O (n)（需辅助数组）。
稳定性：稳定（合并时相等元素按左到右顺序复制）。

适用场景

大规模数据，要求稳定排序（如电商订单按时间和金额排序），或外排序（可分步合并磁盘数据）。

排序算法对比与选择

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
直接插入	O(n²)	O(n²)	O(1)	稳定	小规模 / 部分有序数据
希尔排序	O(n¹·³)	O(n²)	O(1)	不稳定	中大规模乱序数据
冒泡排序	O(n²)	O(n²)	O(1)	稳定	小规模数据 / 教学
快速排序	O(nlogn)	O(n²)	O(logn)	不稳定	大规模乱序数据（实际应用首选）
直接选择	O(n²)	O(n²)	O(1)	不稳定	小规模数据，交换次数敏感
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定	大规模数据，空间敏感
归并排序	O(nlogn)	O(nlogn)	O(n)	稳定	大规模数据，要求稳定排序

选择建议

小规模数据（n≤100）：直接插入或直接选择（实现简单）。
部分有序数据：直接插入（最好 O (n)）。
大规模乱序数据：快速排序（平均最快）、堆排序（空间敏感）、归并排序（需稳定）。
稳定性要求：归并排序、冒泡排序、直接插入排序

排序算法全解析：从原理到应用

排序算法基础概念

内排序与外排序

关键评价指标

插入排序：逐步构建有序序列

1. 直接插入排序

基本思想

示例步骤（以[67, 67, 14, 52, 29, 9, 90, 54, 87, 71]为例）：

代码实现

性能分析

适用场景

2. 希尔排序（缩小增量排序）

基本思想

示例步骤（步长初始为 5）：

代码实现

性能分析

适用场景

交换排序：通过交换纠正逆序

1. 冒泡排序

基本思想

示例步骤：

代码实现

性能分析

适用场景

2. 快速排序

基本思想

示例步骤（基准为 67）：

代码实现

性能分析

适用场景

选择排序：每次选最值放到有序区

1. 直接选择排序

基本思想

示例步骤：

代码实现

性能分析

适用场景

2. 堆排序

基本思想

示例步骤：

代码实现

性能分析

适用场景

归并排序：分而治之的合并策略

基本思想

示例步骤：

代码实现

性能分析

适用场景

排序算法对比与选择

选择建议

示例步骤（以`[67, 67, 14, 52, 29, 9, 90, 54, 87, 71]`为例）：