宝藏速成秘籍（5）插入排序法

一、前言

1.1、概念

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

1.2、排序步骤

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤 2~5。

二、方法分析

插入排序（Insertion Sort）是一种简单直观的排序算法，适合处理小规模数据集。插入排序是一个基础的排序算法，虽然在大规模数据集上性能不佳，但由于其简单性和对小规模或接近有序数据集的高效处理能力，依然在某些应用场景中具有实际价值。理解插入排序的原理和性能分析，可以为学习更复杂的排序算法打下坚实的基础。

三、举例说明

1. 初始数组：[5, 2, 4, 6, 1, 3]
2. 取出2，插入到5前：[2, 5, 4, 6, 1, 3]
3. 取出4，插入到5前：[2, 4, 5, 6, 1, 3]
4. 取出6，保持不变：[2, 4, 5, 6, 1, 3]
5. 取出1，插入到2前：[1, 2, 4, 5, 6, 3]
6. 取出3，插入到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;
            // 将大于key的元素向后移动一位
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            // 将key插入到正确的位置
            arr[j + 1] = key;
        }
    }

    // 主方法，进行测试
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        insertionSort(arr);

        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

运行结果：

五、方法评价

#### 1. 时间复杂度

插入排序的时间复杂度取决于输入数据的初始状态。

-最坏情况时间复杂度: O(n^2)
- 最坏情况发生在数组完全逆序时。每次插入一个新的元素都需要与当前有序部分的所有元素进行比较。
- 例如，对于数组 `[5, 4, 3, 2, 1]`，每插入一个元素，都需要比较 n-1 次、n-2 次，依此类推，总的比较次数为 (1 + 2 + ... + (n-1) = frac{(n-1) \cdot n}{2} = O(n^2)。

-平均时间复杂度: O(n^2)
- 在随机排列的数组上，插入排序的平均时间复杂度也是O(n^2)。

-最好情况时间复杂度: O(n)
- 最好情况发生在数组已经有序时。每次插入元素时，只需要进行一次比较即可。
- 例如，对于数组 `[1, 2, 3, 4, 5]`，每个元素都在其正确位置上，不需要移动。

#### 2. 空间复杂度

-空间复杂度: O(1)

#### 3. 稳定性

-稳定性: 稳定
- 当两个元素相等时，插入排序不会改变它们的相对顺序。

#### 4. 适用场景

插入排序在以下几种情况下表现较好：

-小规模数据集：由于其实现简单，对于小规模数据集插入排序非常高效。
-基本有序的数据集：如果输入数据接近有序，插入排序的性能会接近 \(O(n)\)。
-在线排序：插入排序可以用来处理数据流，当数据是逐个到达时，可以立即进行排序。

#### 5. 优缺点

优点：

- 简单易实现。
- 对于小规模数据集和近似有序的数据集非常高效。
- 原地排序，不需要额外的内存空间。

缺点：

- 对于大规模数据集，时间复杂度较高，不适合使用。
- 与高级排序算法（如快速排序、归并排序）相比，插入排序的性能较差。