《算法第四版》

????通常人們整理橋牌的方法是一張一張的來,將每一張牌插入到其他已經(jīng)有序的牌中的適當(dāng)位置。在計算機的實現(xiàn)中,為了給要插入的元素騰出空間,我們需要將其余所有元素在插入之前都向右移動一位。這種算法叫做插入排序。

????與選擇排序一樣,當(dāng)前索引左邊的所有元素都是有序的,但它們的最終位置還不確定,為了給

更小的元素騰出空間,它們可能會被移動。但是當(dāng)索引到達數(shù)組的右端時,數(shù)組排序就完成了。

????和選擇排序不同的是,插入排序所需的時間取決于輸入中元素的初始順序。例如,對一個很大

且其中的元素已經(jīng)有序(或接近有序)的數(shù)組進行排序?qū)葘﹄S機順序的數(shù)組或是逆序數(shù)組進行

排序要快得多。

????插入排序?qū)τ趯嶋H應(yīng)用中常見的某些類型的非隨機數(shù)組很有效。

java實現(xiàn)：

自己寫的

寫完查了查還有比較好的寫法，參考：http://www.itdecent.cn/p/07b911fb740e