快捷導(dǎo)航

用Java實(shí)現(xiàn)希爾排序的示例

更新時(shí)間：2013年11月14日 11:44:33 作者：

問(wèn)題：現(xiàn)有一段程序S，可以對(duì)任意n個(gè)數(shù)進(jìn)行排序。如果現(xiàn)在需要對(duì)n^2個(gè)數(shù)進(jìn)行排序，最少需要調(diào)用S多少次？只允許調(diào)用S，不可以做別的操作。我們用希爾排序來(lái)做解決這個(gè)

一.理論準(zhǔn)備
希爾排序(Shell Sort)是插入排序的一種，是針對(duì)直接插入排序算法的改進(jìn)，是將整個(gè)無(wú)序列分割成若干小的子序列分別進(jìn)行插入排序，希爾排序并不穩(wěn)定。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。
基本思想：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?BR>希爾排序的時(shí)間性能優(yōu)于直接插入排序的原因：
①當(dāng)文件初態(tài)基本有序時(shí)直接插入排序所需的比較和移動(dòng)次數(shù)均較少。
②當(dāng)n值較小時(shí)，n和n2的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度O(n)和最壞時(shí)間復(fù)雜度0(n2)差別不大。
③在希爾排序開始時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來(lái)增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過(guò)序，使文件較接近于有序狀態(tài)，所以新的一趟排序過(guò)程也較快。
因此，希爾排序在效率上較直接插人排序有較大的改進(jìn)。
增量序列的選擇：Shell排序的執(zhí)行時(shí)間依賴于增量序列。
好的增量序列的共同特征(查到的資料都這么講)：
① 最后一個(gè)增量必須為1；
② 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。
看到了這個(gè)，我想試試希爾排序，就學(xué)學(xué)。

復(fù)制代碼代碼如下:

public class ShellSort {
 public static void main(String[] args) {

  int[] arr = new int[]{44,33,99,10,30,20,59,78,23,48};
  System.out.print("排序前：");
  for(int o: arr) {
   System.out.print(o+" ");
  }
  System.out.println();
  shellSort(arr);
  System.out.print("排序后：");
  for(int o: arr) {
   System.out.print(o+" ");
  }
  System.out.println();
 }
 private static void shellSort(int[] arr) {

  int j;
  int len = arr.length;
  for(int val=len>>1; val>0; val>>=1) {
   //下面是對(duì)本次的所有分組做直接插入排序
   for(int i=val; i<len; i++) {
    int temp = arr[i];
    /*
     * 為什么每次都用temp比較呢？
     * 因?yàn)橹苯硬迦刖褪钦业絫emp的合適位置。
     * 為什么temp<arr[j-val]這個(gè)條件可以放在for內(nèi)呢？
     * 因?yàn)樵瓉?lái)的組內(nèi)數(shù)據(jù)已經(jīng)有序，找到位置就停止便是。
     * 不甚理解的去看直接插入排序吧。
     */
    for(j=i; j>=val&&temp<arr[j-val]; j-=val) {
     /*
      * 為什么是arr[j-val]不是arr[j]呢？
      * 因?yàn)閖=i開始的，而且條件是j>=val&&temp<arr[j-val]
      */
     arr[j] = arr[j-val];
    }
    /*
     * 注意不是arr[i] = temp
     * 直接插入排序也是這樣的。
     * 為什么呢？
     * 因?yàn)閖是位置，i是待插入元素
     */
    arr[j] = temp;
   }
  }
 }
}