一、基本思想

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

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

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

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

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

二、算法描述

假定n是數(shù)組的長度，

首先假設(shè)第一個元素被放置在正確的位置上，這樣僅需從1-n-1范圍內(nèi)對剩余元素進(jìn)行排序。對于每次遍歷，從0-i-1范圍內(nèi)的元素已經(jīng)被排好序，

每次遍歷的任務(wù)是：通過掃描前面已排序的子列表，將位置i處的元素定位到從0到i的子列表之內(nèi)的正確的位置上。

將arr[i]復(fù)制為一個名為target的臨時元素。

向下掃描列表，比較這個目標(biāo)值target與arr[i-1]、arr[i-2]的大小，依次類推。

這個比較過程在小于或等于目標(biāo)值的第一個元素(arr[j])處停止，或者在列表開始處停止(j=0)。

在arr[i]小于前面任何已排序元素時，后一個條件(j=0)為真，

因此，這個元素會占用新排序子列表的第一個位置。

在掃描期間，大于目標(biāo)值target的每個元素都會向右滑動一個位置(arr[j]=arr[j-1])。

一旦確定了正確位置j，

目標(biāo)值target(即原始的arr[i])就會被復(fù)制到這個位置。

與選擇排序不同的是，插入排序?qū)?shù)據(jù)向右滑動，并且不會執(zhí)行交換。

三、示例代碼

四、效率分析

穩(wěn)定

空間復(fù)雜度O(1)

時間復(fù)雜度O(n2)

最差情況：反序，需要移動n*(n-1)/2個元素

最好情況：正序，不需要移動元素

數(shù)組在已排序或者是“近似排序”時，插入排序效率的最好情況運(yùn)行時間為O(n)；

插入排序最壞情況運(yùn)行時間和平均情況運(yùn)行時間都為O(n2)。

通常，插入排序呈現(xiàn)出二次排序算法中的最佳性能。

對于具有較少元素(如n<=15)的列表來說，二次算法十分有效。

在列表已被排序時，插入排序是線性算法O(n)。

在列表“近似排序”時，插入排序仍然是線性算法。

在列表的許多元素已位于正確的位置上時，就會出現(xiàn)“近似排序”的條件。

通過使用O(nlog2n)效率的算法(如快速排序)對數(shù)組進(jìn)行部分排序，

然后再進(jìn)行選擇排序，某些高級的排序算法就是這樣實現(xiàn)的。

總結(jié)

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

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