插入排序

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

工作原理

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

图示

示例

假设有一个待排序的列表：[12, 11, 13, 5, 6]

第一步

• 第一个元素 12 已经排序。

第二步

• 取出 11，与 12 比较，11 小于 12，交换位置。 [11, 12, 13, 5, 6]

第三步

• 取出 13，与 12 比较，13 大于 12，不做交换。 [11, 12, 13, 5, 6]

第四步

• 取出 5，与 13 比较，5 小于 13，交换位置。
• 再与 12 比较，5 小于 12，交换位置。
• 再与 11 比较，5 小于 11，交换位置。 [5, 11, 12, 13, 6]

第五步

• 取出 6，与 13 比较，6 小于 13，交换位置。
• 再与 12 比较，6 小于 12，交换位置。
• 再与 11 比较，6 大于 5，不做交换。 [5, 6, 11, 12, 13]

复杂度分析

• 时间复杂度为 $O(n^2)$、自适应排序：在最差情况下，每次插入操作分别需要循环 $n - 1$、$n-2$、$\dots$、$2$、$1$ 次，求和得到 $(n - 1) n / 2$ ，因此时间复杂度为 $O(n^2)$ 。在遇到有序数据时，插入操作会提前终止。当输入数组完全有序时，插入排序达到最佳时间复杂度 $O(n)$ 。

  • 如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。
  • 最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需 $𝑛−1$ 次即可
  • 最坏情况就是，序列是降序排列，那么此时需要进行的比较共有 $\frac {1}{2}n(n-1)$ 次。
  • 插入排序的赋值操作是比较操作的次数减去$𝑛−1$次，（因为$𝑛−1$次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。
  • 平均来说插入排序算法复杂度为 $O(n^{2})$。

• 空间复杂度为 $O(1)$、原地排序：指针 $i$ 和 $j$ 使用常数大小的额外空间。

• 稳定排序：在插入操作过程中，我们会将元素插入到相等元素的右侧，不会改变它们的顺序。

插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。

时间复杂度

• 最坏情况时间复杂度：$O(n^2)$
• 平均情况时间复杂度：$O(n^2)$
• 最好情况时间复杂度：$O(n)$

空间复杂度

• 空间复杂度：$O(1)$

插入排序的优势

插入排序的时间复杂度为 $O(n^2)$ ，而我们即将学习的快速排序的时间复杂度为 $O(n \log n)$ 。尽管插入排序的时间复杂度更高，但在数据量较小的情况下，插入排序通常更快。

这个结论与线性查找和二分查找的适用情况的结论类似。快速排序这类 $O(n \log n)$ 的算法属于基于分治策略的排序算法，往往包含更多单元计算操作。而在数据量较小时，$n^2$ 和 $n \log n$ 的数值比较接近，复杂度不占主导地位，每轮中的单元操作数量起到决定性作用。

实际上，许多编程语言（例如 Java）的内置排序函数采用了插入排序，大致思路为：对于长数组，采用基于分治策略的排序算法，例如快速排序；对于短数组，直接使用插入排序。

虽然冒泡排序、选择排序和插入排序的时间复杂度都为 $O(n^2)$ ，但在实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序，主要有以下原因。

• 冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高。

• 选择排序在任何情况下的时间复杂度都为 $O(n^2)$ 。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高。

• 选择排序不稳定，无法应用于多级排序。

  代码实现

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

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            // 将 arr[0..i-1] 中大于 key 的元素向后移动一位
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}