快捷導(dǎo)航

Java排序算法總結(jié)之希爾排序

更新時(shí)間：2015年05月19日 10:47:05 作者：一羽清寧

這篇文章主要介紹了Java排序算法總結(jié)之希爾排序,較為詳細(xì)的分析了希爾排序的原理與java的實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了Java排序算法總結(jié)之希爾排序。分享給大家供大家參考。具體分析如下：

前言：希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進(jìn)。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。本文主要介紹希爾排序用Java是怎樣實(shí)現(xiàn)的。

希爾排序(縮小增量法) 屬于插入類排序,是將整個(gè)無序列分割成若干小的子序列分別進(jìn)行插入排序。希爾排序并不穩(wěn)定，O(1)的額外空間，時(shí)間復(fù)雜度為O(N*(logN)^2)。最壞的情況下的執(zhí)行效率和在平均情況下的執(zhí)行效率相比相差不多。

基本思想：

先取一個(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)橹埂?/p>

代碼實(shí)現(xiàn)：

public class Test { 
  public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
  // 預(yù)設(shè)數(shù)據(jù)數(shù)組 
  public static void main(String args[]) { 
    int i; // 循環(huán)計(jì)數(shù)變量 
    int Index = a.length;// 數(shù)據(jù)索引變量 
    System.out.print("排序前: "); 
    for (i = 0; i < Index - 1; i++) 
      System.out.printf("%3s ", a); 
    System.out.println(""); 
    ShellSort(Index - 1); // 選擇排序 
    // 排序后結(jié)果 
    System.out.print("排序后: "); 
    for (i = 0; i < Index - 1; i++) 
      System.out.printf("%3s ", a); 
    System.out.println(""); 
  } 
  public static void ShellSort(int Index) { 
    int i, j, k; // 循環(huán)計(jì)數(shù)變量 
    int Temp; // 暫存變量 
    boolean Change; // 數(shù)據(jù)是否改變 
    int DataLength; // 分割集合的間隔長度 
    int Pointer; // 進(jìn)行處理的位置 
    DataLength = (int) Index / 2; // 初始集合間隔長度 
    while (DataLength != 0) // 數(shù)列仍可進(jìn)行分割 
    { 
      // 對各個(gè)集合進(jìn)行處理 
      for (j = DataLength; j < Index; j++) { 
        Change = false; 
        Temp = a[j]; // 暫存Data[j]的值,待交換值時(shí)用 
        Pointer = j - DataLength; // 計(jì)算進(jìn)行處理的位置 
        // 進(jìn)行集合內(nèi)數(shù)值的比較與交換值 
        while(Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index){ 
          a[Pointer + DataLength] = a[Pointer]; 
          // 計(jì)算下一個(gè)欲進(jìn)行處理的位置
          Pointer = Pointer - DataLength; 
          Change = true; 
          if (Pointer < 0 || Pointer > Index) 
            break; 
        } 
        // 與最后的數(shù)值交換
        a[Pointer + DataLength] = Temp; 
        if (Change) { 
          // 打印目前排序結(jié)果 
          System.out.print("排序中: "); 
          for (k = 0; k < Index; k++) 
            System.out.printf("%3s ", a[k]); 
          System.out.println(""); 
        } 
      } 
      DataLength = DataLength / 2; // 計(jì)算下次分割的間隔長度
    } 
  } 
}

希爾排序幾乎沒有最壞情況，無論是正序、逆序、亂序，所用時(shí)間都不是很多，附加儲(chǔ)存是O(1)，的確非常不錯(cuò)。在沒搞清楚快速排序、堆排序之前，它的確是個(gè)很好的選擇。希望能給你帶來幫助。

希望本文所述對大家的java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: