快捷導(dǎo)航

Java經(jīng)典排序算法之希爾排序詳解

更新時(shí)間：2017年04月05日 14:51:17 作者：歐陽(yáng)鵬

這篇文章主要為大家詳細(xì)介紹了Java經(jīng)典排序算法之希爾排序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

一、希爾排序(Shell Sort)

希爾排序（Shell Sort）是一種插入排序算法，因D.L.Shell于1959年提出而得名。
Shell排序又稱作縮小增量排序。

二、希爾排序的基本思想

希爾排序的中心思想就是：將數(shù)據(jù)進(jìn)行分組，然后對(duì)每一組數(shù)據(jù)進(jìn)行排序，在每一組數(shù)據(jù)都有序之后，就可以對(duì)所有的分組利用插入排序進(jìn)行最后一次排序。這樣可以顯著減少交換的次數(shù)，以達(dá)到加快排序速度的目的。

希爾排序的中心思想：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組。所有距離為dl的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插人排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?br />

該方法實(shí)質(zhì)上是一種分組插入方法。

shell排序的算法實(shí)現(xiàn):

void ShellPass(SeqList R，int d) 
 {//希爾排序中的一趟排序，d為當(dāng)前增量 
  for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當(dāng)前的有序區(qū) 
  if(R[i].key<R[i-d].key){ 
   R[0]=R[i];j=i-d； //R[0]只是暫存單元，不是哨兵 
   do {//查找R[i]的插入位置 
   R[j+d]；=R[j]； //后移記錄 
   j=j-d； //查找前一記錄 
   }while(j>0&&R[0].key<R[j].key)； 
   R[j+d]=R[0]； //插入R[i]到正確的位置上 
  } //endif 
 } //ShellPass 
void ShellSort(SeqList R) 
 { 
 int increment=n； //增量初值，不妨設(shè)n>0 
 do { 
   increment=increment/3+1； //求下一增量 
   ShellPass(R，increment)； //一趟增量為increment的Shell插入排序 
  }while(increment>1) 
 } //ShellSort

注意：

當(dāng)增量d=1時(shí)，ShellPass和InsertSort基本一致，只是由于沒(méi)有哨兵而在內(nèi)循環(huán)中增加了一個(gè)循環(huán)判定條件"j>0"，以防下標(biāo)越界。

三、希爾排序算法分析

1、增量序列的選擇。

Shell排序的執(zhí)行時(shí)間依賴于增量序列。好的增量序列的共同特征如下：
a.最后一個(gè)增量必須為1。
b.應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。

有人通過(guò)大量實(shí)驗(yàn)給出了目前最好的結(jié)果：當(dāng)n較大時(shí)，比較和移動(dòng)的次數(shù)大概在n^1.25到n^1.26之間。

2、Shell排序的時(shí)間性能優(yōu)于直接插入排序。

希爾排序的時(shí)間性能優(yōu)于直接排序的原因如下：
a.當(dāng)文件初態(tài)基本有序時(shí)，直接插入排序所需的比較和移動(dòng)次數(shù)均較少。
b.當(dāng)n值較小時(shí)，n和n^2的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度O(n)和最壞時(shí)間復(fù)雜度O(n^2)差別不大。
c.在希爾排序開(kāi)始時(shí)增量較大，分組較多，每組記錄數(shù)目少，故每組內(nèi)直接插入排序較快，后來(lái)增量d(i)逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按d(i-1)做為距離拍過(guò)序，使文件較接近于有序狀態(tài)，所以新的一趟排序過(guò)程也較快。因此，希爾排序在效率上較直接插入排序有較大的改進(jìn)。

3、穩(wěn)定性

希爾排序是不穩(wěn)定的。

四、算法演練

假定待排序文件由10個(gè)記錄，其關(guān)鍵字分別是：40、38、65、97、76、13、27、49、55、04。
增量序列取值依次為：5、3、1
排序過(guò)程演示如下圖所示：

其動(dòng)畫效果如下面的gif動(dòng)畫所示：

ps:讀者也可以自己打開(kāi)下面的鏈接，自己設(shè)定要排序的數(shù)組，進(jìn)行排序演練
希爾排序動(dòng)畫演示

五、代碼實(shí)現(xiàn)

public class ShellSortTest { 
 private static void shellSort(int[] source) { 
  int j; 
  for (int gap = source.length / 2; gap > 0; gap /= 2) { 
   for (int i = gap; i < source.length; i++) { 
    int temp = source[i]; 
    for (j = i; j >= gap && temp < source[j - gap]; j -= gap) 
     source[j] = source[j - gap]; 
    source[j] = temp; 
   } 
   System.out.print("增長(zhǎng)序列：" + gap + " :"); 
   printArray(source); 
  } 
 } 
 
 private static void printArray(int[] source) { 
  for (int i = 0; i < source.length; i++) { 
   System.out.print("\t" + source[i]); 
  } 
  System.out.println(); 
 } 
 
 public static void main(String[] args) { 
  int source[] = new int[] {49,38,65,97,76,13,27,49,55,04 }; 
  System.out.print("原始序列："); 
  printArray(source); 
  System.out.println(""); 
 
  shellSort(source); 
 
  System.out.print("\n\n最后結(jié)果："); 
  printArray(source); 
 } 
 
}

運(yùn)行結(jié)果為：

原始序列： 49 38 65 97 76 13 27 49 55 4 
 
增長(zhǎng)序列：5 : 13 27 49 55 4 49 38 65 97 76 
增長(zhǎng)序列：2 : 4 27 13 49 38 55 49 65 97 76 
增長(zhǎng)序列：1 : 4 13 27 38 49 49 55 65 76 97 
 
 
最后結(jié)果： 4 13 27 38 49 49 55 65 76 97

發(fā)現(xiàn)增長(zhǎng)序列是5,2,1 和題目要求的5,3,1不同。通過(guò)分析要排序的文件由10個(gè)記錄，10/2=5,5-2=3,3-2=1。剛好符合要求，因此將上面的代碼稍作修改即可改變?cè)鲩L(zhǎng)序列的值。

將shellSort(int[] source) 方法里的下面這行代碼

for (int gap = source.length / 2; gap > 0; gap /= 2) {
改為：
for (int gap = source.length / 2; gap > 0; gap -= 2) {
然后重新運(yùn)行程序，打印結(jié)果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4 
 
增長(zhǎng)序列：5 : 13 27 49 55 4 49 38 65 97 76 
增長(zhǎng)序列：3 : 13 4 49 38 27 49 55 65 97 76 
增長(zhǎng)序列：1 : 4 13 27 38 49 49 55 65 76 97 
 
 
最后結(jié)果： 4 13 27 38 49 49 55 65 76 97

如果想使用指定的增長(zhǎng)序列來(lái)對(duì)指定的數(shù)組進(jìn)行希爾排序，可以對(duì)上面的程序修改，修改后代碼如下：

public class ShellSortTest2 { 
 /** 
  * 待排序的數(shù)組 
  */ 
 private int[] sources; 
 /** 
  * 數(shù)組內(nèi)元素個(gè)數(shù) 
  */ 
 private int itemsNum; 
 /** 
  * 增量數(shù)組序列 
  */ 
 private int[] intervalSequence; 
 
 /** 
  * @param maxItems 
  *   數(shù)組大小 
  * @param intervalSequence 
  *   增量數(shù)組序列 
  */ 
 public ShellSortTest2(int[] source, int[] intervalSequence) { 
  this.sources = new int[source.length]; 
  this.itemsNum = 0;// 還沒(méi)有元素 
  this.intervalSequence = intervalSequence; 
 } 
 
 /** 
  * 希爾排序算法 
  */ 
 public void shellSort() { 
  int gap = 0;// 為增量 
  for (int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++)// 最外層循環(huán)，由增量序列元素個(gè)數(shù)決定 
  { 
   gap = intervalSequence[iIntervalLength]; // 從增量數(shù)組序列取出相應(yīng)的增長(zhǎng)序列 
   int innerArraySize;// 每次內(nèi)部插入排序的元素個(gè)數(shù) 
   if (0 == itemsNum % gap) { 
    innerArraySize = itemsNum / gap; 
   } else { 
    innerArraySize = itemsNum / gap + 1; 
   } 
   for (int i = 0; i < gap; i++) { 
    int temp = 0; 
    int out = 0, in = 0; 
    if (i + (innerArraySize - 1) * gap >= itemsNum) { 
     innerArraySize--; 
    } 
    // 內(nèi)部用插入排序 
    for (int j = 1; j < innerArraySize; j++) { 
     out = i + j * gap; 
     temp = sources[out]; 
     in = out; 
     while (in > gap - 1 && sources[in - gap] > temp) { 
      sources[in] = sources[in - gap]; 
      in = in - gap; 
     } 
     sources[in] = temp; 
    } 
   } 
   System.out.print("增長(zhǎng)序列為: " + gap + " "); 
   this.displayArray(); 
  } 
 } 
 
 /** 
  * 初始化待排序數(shù)組 
  */ 
 public void initArray(int[] array) { 
  for (int i = 0; i < array.length; i++) { 
   sources[i] = array[i]; 
  } 
  itemsNum = array.length; 
 } 
 
 /** 
  * 顯示數(shù)組內(nèi)容 
  */ 
 public void displayArray() { 
  for (int i = 0; i < itemsNum; i++) { 
   System.out.print("\t" + sources[i] + " "); 
  } 
  System.out.println("\n"); 
 } 
 
 public static void main(String[] args) { 
  int[] intervalSequence = { 5, 3, 1 }; 
  int[] source = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 }; 
  ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence); 
  // 初始化待排序數(shù)組 
  ss.initArray(source); 
  System.out.print("原始序列： "); 
  ss.displayArray(); 
  // 希爾排序 
  ss.shellSort(); 
 
  System.out.print("最后結(jié)果： "); 
  ss.displayArray(); 
 } 
}

運(yùn)行結(jié)果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4 
 
增長(zhǎng)序列為: 5 13 27 49 55 4 49 38 65 97 76 
 
增長(zhǎng)序列為: 3 13 4 49 38 27 49 55 65 97 76 
 
增長(zhǎng)序列為: 1 4 13 27 38 49 49 55 65 76 97 
 
最后結(jié)果： 4 13 27 38 49 49 55 65 76 97

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: