彻底掌握插入排序与归并排序 | 学习笔记 / 排序

冒泡排序法（Bubble Sort） 是一种简单的排序算法，它通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置来实现排序。虽然十分直观，但其时间复杂度达到了 $O(n^2)$ 在大多数情况下效率较低，尤其是对于大型数据集来说。此时，插入排序（Insertion Sort） 和 归并排序（Merge Sort） 提供了更高效的替代方案。本文将详细介绍它们的原理、实现及性能分析，帮助读者彻底掌握这两种排序方法。

插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法，它的工作原理类似于整理扑克牌。通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

原理

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描，找到相应位置并插入。
重复步骤 2 和 3，直到所有元素均排序完毕。

插入排序

几种排序演示 你也可以点击上方链接，进入可视化网站亲自体验插入排序的演示

实例

假设有一个待排序的列表 [5, 2, 4, 6, 1, 3]，插入排序的过程如下：

初始状态：
1. 已排序部分：[5]
2. 未排序部分：[2, 4, 6, 1, 3]
第一轮：
1. 取出未排序部分的第一个元素 2
2. 将 2 与已排序部分的 5 比较，2 < 5，插入到 5 前面
3. 已排序部分：[2, 5]
4. 未排序部分：[4, 6, 1, 3]
第二轮：
1. 取出未排序部分的第一个元素 4
2. 将 4 与已排序部分的 5 比较，4 < 5，插入到 5 前面
3. 已排序部分：[2, 4, 5]
4. 未排序部分：[6, 1, 3]
第三轮：
1. 取出未排序部分的第一个元素 6
2. 将 6 与已排序部分的 5 比较，6 > 5，插入到 5 后面
3. 已排序部分：[2, 4, 5, 6]
4. 未排序部分：[1, 3]
第四轮：
1. 取出未排序部分的第一个元素 1
2. 将 1 与已排序部分的 6、5、4、2 依次比较，1 < 2，插入到 2 前面
3. 已排序部分：[1, 2, 4, 5, 6]
4. 未排序部分：[3]
第五轮：
1. 取出未排序部分的第一个元素 3
2. 将 3 与已排序部分的 6、5、4 依次比较，3 < 4，插入到 4 前面
3. 已排序部分：[1, 2, 3, 4, 5, 6]
4. 未排序部分：[]

最终，列表被排序为 [1, 2, 3, 4, 5, 6]。

实现

以下是插入排序的 Java 实现代码：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; 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^2)$ ，最好情况下为 $O(n)$ （当数组已经有序时）。
空间复杂度： $O(1)$ ，因为插入排序是原地排序算法。

稳定性：插入排序是稳定的排序算法。适用场景：适用于小规模数据集或部分有序的数据集。优点：简单易实现，适合小数据集，具有稳定性。缺点：对于大规模数据集效率较低。

归并排序（Merge Sort）

归并排序是一种高效的排序算法，采用分治法（Divide and Conquer）策略。它将待排序的数组分成两半，分别对这两半进行排序，然后将排序好的两半合并在一起。

原理

将数组分成两半，递归地对每一半进行归并排序。
当子数组的大小为 1 时，认为它们已经排序好。
合并两个已排序的子数组，形成一个更大的已排序数组。

归并排序

几种排序演示

实例

假设有一个待排序的列表 [38, 27, 43, 3, 9, 82, 10]，归并排序的过程如下：

初始状态：
- 待排序部分：[38, 27, 43, 3, 9, 82, 10]
分割阶段：
- 将列表分成两半：[38, 27, 43] 和 [3, 9, 82, 10]
- 继续分割：
  - [38, 27, 43] 分成 [38] 和 [27, 43]
  - [27, 43] 分成 [27] 和 [43]
  - [3, 9, 82, 10] 分成 [3, 9] 和 [82, 10]
  - [3, 9] 分成 [3] 和 [9]
  - [82, 10] 分成 [82] 和 [10]
合并阶段：
- 合并 [27] 和 [43] 得到 [27, 43]
- 合并 [38] 和 [27, 43] 得到 [27, 38, 43]
- 合并 [3] 和 [9] 得到 [3, 9]
- 合并 [82] 和 [10] 得到 [10, 82]
- 合并 [3, 9] 和 [10, 82] 得到 [3, 9, 10, 82]
- 最后合并 [27, 38, 43] 和 [3, 9, 10, 82]

得到最终排序结果 [3, 9, 10, 27, 38, 43, 82]

实现

以下是插入排序的 Java 实现代码：

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

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

复杂度分析

时间复杂度：最坏情况下为 $O(n \log n)$ ，平均情况下为 $O(n \log n)$ ，最好情况下为 $O(n \log n)$ 。
空间复杂度： $O(n)$ ，因为归并排序需要额外的存储空间来存放临时数组。
稳定性：归并排序是稳定的排序算法。
适用场景：适用于大规模数据集，尤其是需要稳定排序的场景。
优点：时间复杂度稳定，适合大数据集，具有稳定性。
缺点：需要额外的存储空间，空间复杂度较高。

时间复杂度稳定指的是无论输入数据的初始顺序如何，无论数组每次被分成几部分，归并排序的时间复杂度始终保持在 $O(n \log n)$ ，这使得它在处理各种类型的数据时表现一致。