排序之插入排序

算法

最简单的排序算法之一是插入排序。插入排序由N-1趟排序组成。对于p=1到N-1趟，插入排序保证从位置0到位置p上的元素为排序状态。插入排序利用了这样的事实：已知位置0到位置p-1上的元素已经处于排过序的状态。

Java代码实现

int[] insertionSort(int[] nums) {
    int i;
    for (int p = 1; p < nums.length; p++) {
        int temp = nums[p];
        for (i = p; i > 0 && temp < nums[i - 1]; i--) {
            nums[i] = nums[i - 1];
        }
        nums[i] = temp;
    }
    return nums;
}

分析

由于嵌套循环的每一个花费N次迭代，因此插入排序为O(N²)，而且这个界是精确的，因为以反序的输入可以达到该界限。
Σi = 2 + 3 + 4 +…+ N=O(N²)