快捷導(dǎo)航

java數(shù)據(jù)結(jié)構(gòu)與算法之希爾排序詳解

更新時間：2017年05月03日 10:13:19 作者：android小豬

這篇文章主要介紹了java數(shù)據(jù)結(jié)構(gòu)與算法之希爾排序,結(jié)合實例形式分析了希爾排序的概念、原理、實現(xiàn)方法與相關(guān)注意事項,需要的朋友可以參考下

本文實例講述了java數(shù)據(jù)結(jié)構(gòu)與算法之希爾排序。分享給大家供大家參考，具體如下：

這里要介紹的是希爾排序（縮小增量排序法）。

希爾排序：通過比較相距一定間隔的元素來工作；各趟比較所用的距離（增量）隨著算法的進(jìn)行而減小，直到只比較相鄰元素的最后一趟排序為止。是插入排序的一種，是針對直接插入排序算法的改進(jìn)。

算法思想：先將要排序的序列按某個增量d分成若干個子序列，對每個子序列中全部元素分別進(jìn)行直接插入排序，然后再用一個較小的增量對它進(jìn)行分組，在每組中再進(jìn)行排序。當(dāng)增量減到1時，整個要排序的數(shù)被分成一組，排序完成。注意：增量的取值——一般的初次取序列的一半為增量，以后每次減半，直到增量為1。

算法實現(xiàn)代碼如下：

package exp_sort;
public class ShellSort {
  public static void shell(int array[]) {
    int j;
    int average;
    //設(shè)置增量的值
    for (average = array.length / 2; average > 0; average /= 2) { //步長
      for (int i = average; i < array.length; i++) { //子序列進(jìn)行直接插入排序
        int temp = array[i];
        for (j = i; j >= average && temp < array[j - average]; j -= average) {
          array[j] = array[j - average];
        }
        array[j] = temp;
      }
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    shell(array);
  }
}

算法分析：該算法是按照不同步長對元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ裕?strong>希爾排序的時間復(fù)雜度會比O(n^2)好一些，為O(n^1.5)，排序效率比插入排序高很多。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。希爾排序沒有快速排序算法快 O(N*(logN))，因此對中等大小規(guī)模的數(shù)據(jù)排序比較適用，對規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。但是比O(N^2)復(fù)雜度的算法快得多。并且希爾排序非常容易實現(xiàn)，算法代碼短而簡單。此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時快速排序在最壞的情況下執(zhí)行的效率會非常差。

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

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

您可能感興趣的文章: