北京北大青鳥學(xué)校講解：插入排序

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

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]應(yīng)該擺放的位置，此處可以利用查找算法進(jìn)行優(yōu)化 
05 if(j < i){ 
06 //將j之后的數(shù)據(jù)移動(dòng)一位，然后把elements[i]移動(dòng)到j(luò)處 
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 }(北大青鳥課程)

北京北大青鳥學(xué)校介紹另一種常用的插入排序算法：Shell排序也是對直接插入排序算法的一種優(yōu)化，因此可以說直接插入排序是一種特殊的Shell排序，Shell排序?qū)χ苯硬迦肱判虻膬?yōu)化主要體現(xiàn)在，Shell排序通過使用一個(gè)增量序列（遞減），每次把要排序的數(shù)組分成幾個(gè)子數(shù)組，然后對子數(shù)組進(jìn)行插入排序，這樣可以減少比較和移動(dòng)數(shù)據(jù)的次數(shù)，Shell排序是一種非常高效的排序算法，該算法的思想是：

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

Shell排序的Java實(shí)現(xiàn)如下：
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]應(yīng)該擺放的位置 
07 if(j < i){ 
08 //將j之后的數(shù)據(jù)移動(dòng)h位，然后把elements[i]移動(dòng)到j(luò)處 
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 }(北大青鳥課程)
文章由北京北大青鳥學(xué)校學(xué)術(shù)部老師提供