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

插入排序（Insertion Sort）

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

原理

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

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

实例

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

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

复杂度分析

• 时间复杂度：最坏情况下为 ，平均情况下为 ，最好情况下为 （当数组已经有序时）。
• 空间复杂度：，因为插入排序是原地排序算法。

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

归并排序（Merge Sort）

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

原理

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

实例

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

1. 初始状态：
   • 待排序部分：[38, 27, 43, 3, 9, 82, 10]
2. 分割阶段：
   • 将列表分成两半：[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]
3. 合并阶段：
   • 合并 [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++;
        }
    }
}

复杂度分析

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

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