背景介紹

是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 ----- 來自?wikipedia

算法規(guī)則

一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：

1.從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序

2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

3. 如果該元素（已排序）大于新元素，將該元素移到下一位置

4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置將

5. 新元素插入到該位置后

6.重復(fù)步驟2~5

復(fù)雜度

插入排序當(dāng)中有兩個(gè)循環(huán)，假設(shè)數(shù)組的大小為n，則第一個(gè)循環(huán)是n－1次，第二個(gè)while循環(huán)在最壞的情況下是1到n－1次。因此插入排序的時(shí)間復(fù)雜度大約為如下形式：

1+2+3+4+...＋n－1 ＝ n（n－1）/ 2 ＝ O（n2），時(shí)間復(fù)雜度為輸入規(guī)模的2次函數(shù)，可見插入排序的時(shí)間復(fù)雜度是比較高的。這是原理上的簡(jiǎn)單分析，最后在“算林大會(huì)”中，各位可以清楚的看到插入排序隨著輸入規(guī)模的增長(zhǎng)，時(shí)間會(huì)指數(shù)倍的上升。

代碼實(shí)現(xiàn)（Java版本）