北京北大青鳥學校講解：插入排序

什么是插入排序？北京北大青鳥學校學術老師講解：插入排序是一種通過不斷地把新元素插入到已排好序的數據中的排序算法，常用的插入排序算法包括直接插入排序和shell排序，直接插入排序實現比較簡單，時間復雜度是O（n），但是直接插入沒有充分的利用已插入的數據已經排序這個事實，因此有很多針對直接插入排序改進的算法，例如折半插入排序等，下邊是直接插入排序的Java實現：(北大青鳥課程)

view sourceprint?
01 public static void insertSort(int[] elements){ 
02 for(int I = 1;I <elements.length; i++){ 
03 int j = -1; 
04 while(j <= I && elements[i] > elements[++j]);//找到element[i]應該擺放的位置，此處可以利用查找算法進行優化 
05 if(j < i){ 
06 //將j之后的數據移動一位，然后把elements[i]移動到j處 
07 int temp = elements[i]; 
08 for(int k = i-1;k >= j;k--){ 
09 elements[k+1] = elements[k]; 
10 } 
11 elements[j] = temp; 
12 } 
13 } 
14 }(北大青鳥課程)

北京北大青鳥學校介紹另一種常用的插入排序算法：Shell排序也是對直接插入排序算法的一種優化，因此可以說直接插入排序是一種特殊的Shell排序，Shell排序對直接插入排序的優化主要體現在，Shell排序通過使用一個增量序列（遞減），每次把要排序的數組分成幾個子數組，然后對子數組進行插入排序，這樣可以減少比較和移動數據的次數，Shell排序是一種非常高效的排序算法，該算法的思想是：

1.以h（h一般取n/2）為間隔將n個元素列分為幾個小組，在每個小組內按直接插入法排序
2.令h=h/2，重復第1步
3.當h=1時，排序結束（此時相當于直接插入排序，不過由于數據已經基本排好序，因此比較次數和移動次數比直接插入排序少很多）

Shell排序的Java實現如下：
view sourceprint?
01 public static void shellSort(int[] elements){ 
02 for(int h = elements.length/2;h > 0;h /= 2){ 
03
04 for(int i = h;i < elements.length; i++){ 
05 int j = i % h; 
06 while(j <= i && elements[i] > elements[j]) j += h;//找到element[i]應該擺放的位置 
07 if(j < i){ 
08 //將j之后的數據移動h位，然后把elements[i]移動到j處 
09 int temp = elements[i]; 
10 for(int k = i-h;k >= j;k -= h){ 
11 elements[k+h] = elements[k]; 
12 } 
13 elements[j] = temp; 
14 } 
15 } 
16
17 } 
18 }(北大青鳥課程)
文章由北京北大青鳥學校學術部老師提供