通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)的位置并插入。

插入排序非常類似于整撲克牌

在開始摸牌時，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進行比較。無論什么時候，左手中的牌都是排好序的。


如果輸入數(shù)組已經(jīng)是排好序的話，插入排序出現(xiàn)最佳情況，其運行時間是輸入規(guī)模的一個線性函數(shù)。如果輸入數(shù)組是逆序排列的，將出現(xiàn)最壞情況。平均情況與最壞情況一樣，其時間代價是Θ(n2)。


也許你沒有意識到，但其實你的思考過程是這樣的：現(xiàn)在抓到一張7，把它和手里的牌從右到左依次比較，7比10小，應(yīng)該再往左插，7比5大，好，就插這里。為什么比較了10和5就可以確定7的位置？為什么不用再比較左邊的4和2呢？因為這里有一個重要的前提：手里的牌已經(jīng)是排好序的?，F(xiàn)在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌還可以用這個方法插入。編程對一個數(shù)組進行插入排序也是同樣道理，但和插入撲克牌有一點不同，不可能在兩個相鄰的存儲單元之間再插入一個單元，因此要將插入點之后的數(shù)據(jù)依次往后移動一個單元。

java實現(xiàn)代碼

package arithmetic.sort.insert; /*** 插入排序* */ public class InsertSort {/*** 算法實現(xiàn)* */public static void sort(int array[]){if( array == null || array.length == 0 ){return ;}int target;int j;for(int i = 1 ; i < array.length ; i++){j = i ;target = array[j];while( j > 0 && array[j-1] > target ){array[j] = array[j-1] ;--j;}array[j] = target;}}/*** 輸出數(shù)組* */public static void show(int array[]){if( array == null || array.length == 0 ){return ;}for(int i = 0 ; i < array.length ; i++){System.out.print( array[i] +" ");}}public static void main(String args[]){ // int[] a = {1,23,4,6,235,74,983,11,22,33,45,55,77,88,9,10}; //有問題int[] a = {4,3,1,2};InsertSort.sort(a);InsertSort.show(a);}}

總結(jié)

以上是生活随笔為你收集整理的三 插入排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。