插入排序

插入排序的代碼實現(xiàn)雖然沒有冒泡排序和選擇排序那么簡單粗暴，但它的原理應(yīng)該是最容易理解的了，因為只要打過撲克牌的人都應(yīng)該能夠秒懂。當(dāng)然，如果你說你打撲克牌摸牌的時候從來不按牌的大小整理牌，那估計這輩子你對插入排序的算法都不會產(chǎn)生任何興趣了.....

算法簡介

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

算法描述和實現(xiàn)

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

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

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

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

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

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

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

實現(xiàn)代碼

測試結(jié)果