快捷導(dǎo)航

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

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

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

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

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

希爾排序：通過比較相距一定間隔的元素來(lái)工作；各趟比較所用的距離（增量）隨著算法的進(jìn)行而減小，直到只比較相鄰元素的最后一趟排序?yàn)橹埂Ｊ遣迦肱判虻囊环N，是針對(duì)直接插入排序算法的改進(jìn)。

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

算法實(shí)現(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) { //步長(zhǎng)
      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);
  }
}

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

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

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

您可能感興趣的文章: