java排序之插入排序（直接插入排序和希爾排序）

上面一片博文探讨了關于的java選擇排序（冒泡排序和快速排序）本章将繼續探讨java排序之插入排序，插入排序分為直接插入排序和希爾排序兩種。

1.直接插入排序思想：在需要排序的一組資料中假設前該數組的前n-1（n >= 2）個數是已經排好序的,現在要把第n個數插入到前面的n-1個數中，使得這n個數也是排好順序的。如此反複進行，知道n等于需要排序的數組的長度時。就實作了該數組的直接插入排序。

代碼如下：

    /**

* 

* @param a 需要排序的數組

*/

public static void simpleSort(int[] a){

   for(int i = 1;i<a.length;i++){//外層for循環從1開始

      int temp = a[i];

      int j = i-1;

      for(;j>=0 && temp < a[j];j--){

       a[j+1] = a[j];

      }

     a[j+1] = temp;

   }

}

//代碼解釋：

例如：需要排序的數組int[] a = {49,38,65,97,76,13,27};

第一次執行該方法執行for循環。

    i=1，temp=38，j=0，a[j]= 49 38 < 49 滿足for(;j>=0 && temp < a[j];j--)條件

    執行a[j+1] = a[j]即a[1] = a[0] 執行後數組為a=[49,49,65,97,76,13,27] 

執行j--，執行後j=-1 跳出内部for循環

執行a[j+1] = temp; j=-1 是以 a[0] = 38;

完成第一次循環後 數組a=[38,49,65,97,76,13,27]

第二次執行外部循環

i=2，temp=65，j=1，a[j]=49 65 > 49 不滿足内部for循環條件直接跳出

執行 a[j+1] = temp; 即a[2]=65

完成第二次循環後 數組a=[38,49,65,97,76,13,27]

第三次外部循環

i=3，temp=97，j=2，a[j]=65 97 > 65 不滿足内部for循環條件直接跳出

執行a[j+1] = temp;即a[3] = 97

完成第三次循環後 數組a=[38,49,65,97,76,13,27]

第四次外部循環

i=4,temp=76,j=3,a[j]=97 76 < 97 滿足内部for循環條件

執行a[j+1] = a[j];即a[4] = a[3] 執行後數組為a=[38,49,65,97,97,13,27]

執行j--，執行後j=2 a[j]=65 76 > 65 不滿足繼續執行内部for循環的條件 直接跳出

執行a[j+1] = temp;即a[3] = 76

完成第四次循環後 數組a=[38,49,65,76,97,13,27]

第五次外部循環

i=5,temp=13,j=4,a[j]=97 13 < 97 滿足内部for循環條件

執行a[j+1] = a[j];即a[5] = a[4] 執行後數組為a=[38,49,65,76,97,97,27]

執行j--，執行後j=3，a[j]=76 13 < 76 滿足内部for循環條件

執行a[j+1] = a[j];即a[4] = a[3] 執行後數組為a=[38,49,65,76,76,97,27]

執行j--，執行後j=2 a[j]=65 13 < 65 滿足内部for循環條件

執行a[j+1]=a[j];即a[3] = a[2] 執行後數組a=[38,49,65,65,76,97,27]

執行j--，執行後j=1 a[j]=49 13 < 49 滿足内部for循環條件

執行a[j+1]=a[j];即a[2]=a[1] 執行後數組為a=[38,49,49,65,76,97,27]

執行j--，執行後j=0，a[j] = 38,13 < 38 滿足内部for循環條件

執行a[j+1]=a[j];即a[1] = a[0] 執行後數組為a=[38,38,49,65,76,97,27]

執行j--，執行後j=-1，不滿足内部for循環條件跳出循環

執行a[j+1] = temp;即a[0]=13 執行後數組a=[13,38,49,65,76,97,27]

完成第五次循環 。

依次循環直到跳出外部for循環整個數組排序完成。

2.希爾排序法

 2.1實作思想  

  在直接插入排序算法中，每次插入一個數。使有序序列 隻增加幾個節點，而且對插入下一個數沒有提供任何幫助。如果比較相隔較遠（稱為增量）的兩個數，使得數移動時能跨過多個數，則進行一次比較就可能消除多個元素交換。D.L.Shell于1959年以他的名字命名的排序算法中實作了這一思想。算法先将要排序的一組數按照某個增量d分成若幹組，每組中元素的下标相差d。對每組中全部元素進行排序，然後在用一個較小的分量（較小的分量一般取目前分量的一半d/2）對排序後的的 整個數組進行分組。再對每組進行排序。當增量d=1時，整個要排序的數組本分成一個數組，然後進行排序，排序即可完成。

 2.2曆史背景

  直接插入排序它的效率在某些時候是很高的，比如我們的元素本身就是基本有序的，我們隻需要少量的插入操作，就可以完成整個數組的排序工作。此時直接插入很高效。還有就是資料比較少時，直接插入的優勢也比較明顯。可問題在于兩個條件本身過于苛刻，現實中資料少和基本有序都屬于特殊情況。有條件當然是好的，條件不存在我們創造條件也要去做，于是科學家D.L.Shell研究出一種排序算法，對直接插入排序改進後可以提高效率。

  如何然待排序的資料少呢？很容易想到就是将原本有大量資料的數組進行分組，分割成若幹個子序列，此時每個子序列的資料就比較少。然後在這些子序列内分别進行直接插入排序，當整個序列都基本有序時，在對全體記錄進行一次直接插入排序。問題其實也就在這裡，我們分隔待排序數組的目的就是為了減少資料的量，對每個子序列進行直接插入排序就是為了讓整個數組基本有序。

  例如數組a=[9,1,5,8,3,7,2,4,6]現在将他按前後順序分為三組a1=[9,1,5]，a2=[8,3,7],

a3=[2,4,6],将三個子序列a1,a2,a3排序後重新組合在一起後a=[1,5,9,3,7,8,2,4,6],此時這個數組還是雜亂無序的，根本談不上基本有序，要排序還是直接重來一遍插入排序。這樣做隻是瞎子戴眼鏡多餘的圈圈，毫無用處，所謂基本有序不是局部有序而是小的資料基本在前面，大的的資料基本在後面，不大不小的資料基本在中間，是以我們會發現将一組需要排序的資料按照先後順序分組排序後滿足不了我們的要求。是以我們需要采取跳躍分割的政策：将相距某個“增量”的資料組成一個子序列，這樣才能保證在子序列内分别進行插入排序後得到的結果是一個基本有序的數組而不是一個局部有序的數組。

   代碼實作：

public static void shellSort(int[] a){

    int j;

    int len = a.length;

    for(int d = len >> 1;d > 0;d = d >> 1 ){

        for(int i = d;i<len;i++){

            int temp = a[i];

            for(j = i; j >= d && temp < a[j-d]; j -= d){

                a[j] = a[j-d];

            }

            a[j] = temp;

        }

    }

代碼執行解釋：

例如：需要排序的數組int a=[56,23,88,15,69,55,11]

   執行int len = a.length; len=7;

    執行第一個for循環 d=3，

    執行内部for(int i = d;i<len;i++)循環；

     i=3，temp=a[i]=15;

     執行内部for(j = i;j>=d && temp < a[j-d];j-=d)循環；

        j=3，temp<a[j-d]即15<a[3-3]=a[0]=56 成立

        執行a[j] = a[j-d];即a[3] = a[0]

        執行j-=d；即j=j-3=0；不滿足for(j = i;j>=d && temp < a[j-d];j-=d)

                    條件跳出循環

       執行a[j]=temp;此時j=0；即a[0] = temp=15;

       該輪最裡層for循環執行完後數組a=[15,23,88,56,69,55,11]

    執行i++，for(int i = d;i<len;i++)第二次循環

    i=4，temp=a[i]=69 執行for(j = i;j>=d && temp < a[j-d];j-=d).........；

    重複上述操作，直到結束for(int i = d;i<len;i++)循環。

執行 d=d/2=1，開始最外層第二次循環。

最外層for循環結束後完成整個方法的調用。完成數組的排序