算法

最簡(jiǎn)單的排序算法之一是插入排序。插入排序由N-1趟排序組成。對(duì)于p=1到N-1趟，插入排序保證從位置0到位置p上的元素為排序狀態(tài)。插入排序利用了這樣的事實(shí)：已知位置0到位置p-1上的元素已經(jīng)處于排過(guò)序的狀態(tài)。

Java代碼實(shí)現(xiàn)

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;
}

分析

由于嵌套循環(huán)的每一個(gè)花費(fèi)N次迭代，因此插入排序?yàn)镺(N²)，而且這個(gè)界是精確的，因?yàn)橐苑葱虻妮斎肟梢赃_(dá)到該界限。
Σi = 2 + 3 + 4 +…+ N=O(N²)