阅读经典——《算法导论》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循环，导致整体上运行时间正比于n2，记做Θ(n2)。
但插入排序也有一些优点：它是原址排序，重排操作基本上在原数组中进行，最多只有常数个字存储在数组外；它是非随机化算法，算法的运行时间对给定的输入是固定的。
获取文集中的全套源码请访问GitHub代码仓库Algorithm。
