java 插入排序_插入排序過程、時間複雜度分析

插入排序是一個重要的排序算法，其思想類比于打撲克牌時候調整手牌的政策。

一、插入排序過程

大學大學期間在資料結構與算法課中，應該都學習過插入排序算法的過程與時間複雜度。下面簡單來複習一下插入排序算法的過程與時間複雜度。

1. 插入排序過程

假設對n個元素進行插入排序，則需要進行n-1趟排序。

示例代碼如下所示，使用java書寫的，可以很容易改為c代碼和python代碼，大家可以進行簡單的調式深刻了解插入排序的過程。

public 
           

從上面的過程我們可以看到，插入排序的過程分為兩步：

• 首先和目前位置的前一個元素進行比較，如果前一個元素比目前元素大，則後續進行調整，将前面的大元素不斷向後移動，并找到合适的位置将目前元素插入進去；
• 如果發現前一個元素比目前元素小，則不會進行調整，預設前面的元素已經有序。

這樣的兩步就是内循環和外循環，後續我們會有插入排序的正确性的證明，也是通過這樣兩步進行證明其正确性。

基于這樣的過程我們很容易分心排序算法的最好情況和最壞情況。

• 最好情況：元素升序有序。那麼我們隻需要進行n-1次元素比較，0次元素移動即可。
• 最壞情況：元素降序有序。那麼我們需要進行

  

  次元素比較，同樣次數的元素移動。

那麼我們已經清楚了最好情況和最壞情況的時間複雜度，那麼平均時間複雜度應該是什麼量級呢？

二、插入排序算法時間複雜度分析

首先，分析平均時間複雜度，我們有兩個假設的前提。

1. All permutation of the keys are equally likely as input.

2. Keys are distinct.

我們進行平均時間複雜度分析時，

思路是

：

分别求每趟排序的平均時間開銷，再

計算得到結果。

小前提：因為移動次數小于比較次數，不是每個比較操作都會發生移動，是以我們将比較次數作為衡量算法時間複雜度的名額。

分析：

在插入下表為i的元素的時候（假設該元素為x），

已經有序了，那麼x實際上有n+1個備選位置可以插入，按照獨立分布來說，每個位置的機率都是1/(i+1)，那麼這n+1個位置從左到右對應的比較次數為（i，i，i-1，...，1）。那麼我們就可以得到一趟插入排序的平均時間複雜度為

接下來，我們将n-1趟結果進行加和，得到最終的平均時間複雜度。

因為lnn與n^2不是一個量級的，這樣我們就可以知道，插入排序法的平均時間複雜度是

量級。

插入排序适合于小序列的排序，當序列長度小于等于20或20左右時，使用插入排序效率更高。

三、插入排序的性能分析

性能分析的目的是讨論是否有方法能對算法進行改進，以提高其平均時間複雜度。

接下來對插入排序進行性能分析：

插入排序的特點是：基于比較、資料移動完成排序 一次比較操作後不發生資料移動或僅僅交換一對相鄰的資料元素。

我們的問題是，此類算法是否可以改進？

分析過程：

n個資料元素有n！個不同的排列組合序列。随機給一個序列

，我們稱

為逆序，共有四個逆序。插入排序的核心想法就是通過元素比較，消除這四個逆序，這樣就達到了排序的目的。

我們已知基于比較的排序算法，一次最多隻能消除一對逆序關系，這樣進一步我們可以知道有多少對逆序，至少需要多少次比較。

n個資料元素，降序有序，是最壞的逆序情況，逆序數量最多有n(n-1)/2個。是以，一個基于比較的排序算法，最壞情況下，最少需要n(n-1)/2次比較。

是以最壞情況時間複雜度W(n)無法再改進了。

下面分析平均情況：

平均情況下，一個序列的逆序數量是不确定的，但是我們可以構造一個與原序列完全相反的序列，x1 =(2, 4, 1, 5, 3),x2 = (3, 5, 1, 4, 2)這兩個序列總逆序的數量等于n(n-1)/2，則平均一個序列的逆序數量是n(n-1)/4個，那麼平均情況也至少需要n(n-1)/4次比較操作，是以平均情況時間複雜度O(n)也沒有将n^2降低的可能性。

定理

任何一個基于關鍵字的比較且每一次比較最多消除一個逆序的排序算法，最壞的情況下至少比較n(n-1)/2次，平均情況至少比較n(n-1)/4次。

四、算法分析及相關問題

算法的評價準則：

1. 正确性：一般使用數學歸納法，證明對于每一個合法的輸入，在有效時間内，算法都會給出一個滿足要求的結果。
2. 空間複雜度
3. 時間複雜度
4. 簡單性、清晰性
5. 優化

算法分析種常見的時間複雜性函數

時間複雜性函數