關于插入排序的分析及構想

顏文巖 劉朝元 吳彩蓮

摘要：在排序中分為內排序和外排序，而我們今天要做的插入排序在排序過程中，整個表都放在內存中處理，排序時不涉及數據內存與外存之間的交換，因此也被稱為內排序。插入排序的基本思想是每次將一個待排序的元素按其關鍵字大小插入到前面已經排好序的子表中的適當位置，直到全部元素插入完為止。

插入排序的分類

插入排序的方法非常之多，今天我們主要研究這三種：

第一種：直接插入排序;

第二種：折半插入排序;

第三種：希爾排序;

...

直接插入排序

假使我們將所有待排序的元素放在一個一維數組a[]中，那么在排序過程中會產生兩個區域。一部分是已經經過直接插入排序的區域，該部分區域內的元素有序排列，但相對于整體來說只能認為是局部有序;另一部分是還未進行排序的區域，該部分區域內的元素無序排列。這種方法也被叫做增量發，它使有序區每次增加一個元素，只有當最后一個元素也進行排序后整個數組才是全局有序的。

但是由于直接插入排序是每一個元素都要與之前進入有序區的元素進行比較，隨著有序區元素的增多，計算量也在不斷的增大。算法的最小時間復雜度為O（n），算法的最大時間復雜度為O（n2），算法的平均時間復雜度為O（n2）

但值得一提的是——直接插入排序算法中只使用了三個輔助變量因此可以說是一個就地排序算法。

折半插入排序

與直接插入排序一樣，折半插入排序也是將所有數據放入一個一維數組a[]中，并在排序過程中將所有元素分為有序區與無序區。但與之區別的是，在程序運行過程中無序區被選中排序b的元素在進入有序區進行排序時并不是一個接一個進行順序比較。而是，因為有序區的元素都是局部有序的，所以b與有序區的中間位置的元素也就是此部分的中位數c進行比較，來決定下一個比較的對象是在c的左側還是右側，這種方法與二叉樹排序的思想非常相似所以也被稱為二分插入排序。

實際上，折半插入排序和直接插入排序比較來看，需要移動的元素并沒有減少，的但這并不是說折半插入排序和直接插入排序就可以畫等號。

就事實而言，折半插入排序的平均時間復雜度也為O（n2），但是折半查找時的比較次是直接順序比較的一半，盡管折半插入排序也屬于直接插入排序，折半插入排序的空間復雜程度為O（1），但是性能要優于直接插入查找。

希爾排序

希爾排序盡管也是一種插入排序，并且也用了數組的思想。但是不是在一維數組是而是二維數組，并且對所有元素金星分組插入。其具體操作方法為——建立設一個a[i][j]。i表示所分的組，j是每個組內的元素個數。

在每一個小分組內，元素的排序是按照直接插入排序使每個分組局部有序，所以要想所有的元素全部有序，就需要不斷的重復上述操作，并且將組數減少，使每個組內的元素逐漸增多，每一次都對其重新排序。直到將二維數組轉變為一維數組，這時進行最后一次組內排序后，整體變為有序數組。

因此，希爾排序也被稱為減少增量的排序方法，在希爾排序每趟完成后數據越來越接近有序。

希爾排序的平均時間復雜度為O（n1.3），從平均時間復雜度上就可以直觀的看出希爾排序要遠遠優于直接插入排序和折半插入排序。但當增量為一時，希爾排序與直接插入排序基本一致，但希爾排序在效率上較直接插入排序在效率上更加簡潔高效，并且減少了時空開銷，大大減少了計算機的運算負擔。

自我分析

在看完上述這三個經典的案例之后，有沒有一個想法，那就是直接插入排序、折半插入排序還有折半查入排序能否在進一步優化呢？答案是肯定的。所以我在想如果有n個元素那么必然有兩種情況：第一種，這n個元素是連續的;第二種，這n個元素不是連續的。

當n個元素連續時，我們不妨將n個元素放入一個a[m][n]的二維數組中，并在定義一個空的大小一樣的二維數組。第一步，將數組的每一行進行從小到大直接排列;第二步，將所有的每一行的最小元素與最大元素分別放進定義的min[]和max[]，第三部，找出min[m]中最小的將它所在的行與第m=0行交換，找出max[m]中最大的將它所在的行與第m=m行交換，前提是這來兩個元素不在同一行，如果在同一行將啊a[m][0]與a[m][n]交換。第四步，將a[0][0]/n==ys，將判斷a[m][n]-a[0][0]是否等于n-1;如果是，那么這組元素就是連續的，如果否。當為是時，將原來a[m][n]中的每一個元素除以n再減去ys得到元素行號，并將之順序放入。第五步，全部放入后在進行一次行內排序，整個數組就變為有序的了。當為否時，運用希爾排序。在這種方法下，如果元素是連續的那么平均時間復雜度為O（n），因此，也可以在一定的方式下加快運算的速率。

那么在這時最大的問題就是如何進行分組，當數據過大時分組的組數就成了一個尤為頭疼的問題，以2進制來看，找到一個2n最接近元素個數的數，以n作為組數。

總結

內排序是快速搜索的重要一環，因為內存的運算速度快造價高昂，決定了他的存儲容量不可能想外存那樣大，所以為了不造成計算機運行的擁堵，內存必須保持一定的容量，這時候時間復雜度與運算的時間就顯得尤為重要。早一點完成就可以早一點轉出內存，騰出更多的空間，使計算機更加流暢。

數據如果在使用的時候是無序的，在使用時查找起來會花費大量的時間，降低用戶體驗，隨著現在數據傳輸速率的加快也更容易造成卡頓。

參考文獻

《數據結構教程（第5版）》李春葆

《插入排序法研究（1）》唐開山

《數據結構與算法詳解》陳銳