阅读经典——《算法导论》01

从本文开始，关注算法领域最基本的问题——排序问题：

输入：n个数的一个序列<a1, a2, ..., an>。
输出：输入序列的一个排列<a1', a2', ..., an'>，满足a1'≦a2'≦...≦an'。

本文介绍一种常用的排序算法——插入排序。该算法适用于对少量元素的排序。

插入排序

原理：
插入排序的原理像人们排序一手扑克牌。每次从桌上摸一张牌并插入到左手已经排好序的手牌中，为了找到正确的插入位置，我们会从右到左将其与左手中的每张牌做比较，直到找到合适的位置。

排序过程如下图所示。

插入排序

算法：
虽然《算法导论》书中采用了伪代码，但为了更贴近实际，本文集中系列文章将使用Java代码重新实现。

/**
 * 插入排序，排序结果仍保存于arr参数中。
 * @param arr 需要排序的数组
 */
public void insertionSort(int[] arr) {
    for (int j = 1; j < arr.length; j++) {
        int key = arr[j];
        //Insert arr[j] into the sorted sequence arr[1..j-1].
        int i = j - 1;
        while (i >= 0 && arr[i] > key) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = key;
    }
}

（注意：由于《算法导论》书中的伪代码的数组下标从1开始，但Java中的数组下标从0开始，因此本系列文章代码以外的部分包括代码注释与书中保持一致，下标从1开始。）

完整代码请参考InsertionSort.java。

分析：

插入排序使用了增量方法，在排序好子数组A[1..j-1]后，将A[j]插入到子数组中的适当位置。

增量法往往是最容易想到的方法，但效率不高。在最坏的情况下，n次for循环中每次嵌套j次while循环，导致整体上运行时间正比于n²，记做Θ(n²)。

但插入排序也有一些优点：它是原址排序，重排操作基本上在原数组中进行，最多只有常数个字存储在数组外；它是非随机化算法，算法的运行时间对给定的输入是固定的。

关注作者或文集《算法导论》，第一时间获取最新发布文章。

获取文集中的全套源码请访问GitHub代码仓库Algorithm。