插入排序的算法描述

插入排序是最简单的排序算法之一。由N-1趟排序组成，对于第p趟排序，插入排序保证从位置0到位置p上的元素为已经排序的状态。这保证了，当进行第p趟排序的时候，位置0到位置p的元素已经处于一个有序状态。下图展示了长度为6的数列进行5趟插入排序后的结果：

在第p趟，我们将位置p上的元素向左移动，插入至前p+1个位置中正确的位置。

代码

class insertionSort{
    void sort(int[] nums){
        int n = nums.length;
        for(int p = 1; p < n; p++){
            int waitToInsert = nums[p];
            int i = p;
            for(; i>0&&nums[i-1]>waitToInsert; i--){    // i从p开始向前找，对于比waitToInsert大的数，向后移动一个位置
                nums[i] = nums[i-1];
            }
            nums[i] = waitToInsert;
        }
    }
}

复杂度分析

由于嵌套循环的每一次都花费N次迭代，因此插入排序为O(N)。