快捷導(dǎo)航

使用Java實現(xiàn)希爾排序算法的簡單示例

更新時間：2016年05月04日 17:19:02 作者：apei830

這篇文章主要介紹了使用Java實現(xiàn)希爾排序算法的簡單示例,希爾排序可以被看作是插入排序的一種更高效的改進(jìn)版本,需要的朋友可以參考下

簡介
希爾排序(縮小增量法) 屬于插入類排序,由Shell提出，希爾排序?qū)χ苯硬迦肱判蜻M(jìn)行了簡單的改進(jìn)：它通過加大插入排序中元素之間的間隔，并在這些有間隔的元素中進(jìn)行插入排序，從而使數(shù)據(jù)項大跨度地移動，當(dāng)這些數(shù)據(jù)項排過一趟序之后，希爾排序算法減小數(shù)據(jù)項的間隔再進(jìn)行排序，依次進(jìn)行下去，進(jìn)行這些排序時的數(shù)據(jù)項之間的間隔被稱為增量，習(xí)慣上用字母h來表示這個增量。
常用的h序列由Knuth提出，該序列從1開始，通過如下公式產(chǎn)生：

h = 3 * h +1

反過來程序需要反向計算h序列，應(yīng)該使用

h=(h-1)/3

代碼實現(xiàn)
實現(xiàn)代碼1：

public static void shellSort(int[] arr){
  int temp;
  for (int delta = arr.length/2; delta>=1; delta/=2){               //對每個增量進(jìn)行一次排序
    for (int i=delta; i<arr.length; i++){       
      for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //注意每個地方增量和差值都是delta
        temp = arr[j-delta];
        arr[j-delta] = arr[j];
        arr[j] = temp;
      }
    }//loop i
  }//loop delta
}

實現(xiàn)代碼2：

public static void shellSort2(int[] arr){
  int delta = 1;
  while (delta < arr.length/3){//generate delta
    delta=delta*3+1;  // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
  }    
  int temp;
  for (; delta>=1; delta/=3){
    for (int i=delta; i<arr.length; i++){       
      for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){
        temp = arr[j-delta];
        arr[j-delta] = arr[j];
        arr[j] = temp;
      }
    }//loop i
  }//loop delta
}

上面程序在和直接插入法比較，會發(fā)現(xiàn)其與直接插入排序的差別在于：直接插入排序中的h會以1代替。
Shell排序是不穩(wěn)定的，它的空間開銷也是O(1),時間開銷估計在O(N3/2)~O(N7/6)之間。

您可能感興趣的文章:

相關(guān)文章

Java深入淺出理解快速排序以及優(yōu)化方式
快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用，再加上快速排序思想----分治法也確實實用，因此很多軟件公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個，還有大大小的程序方面的考試如軟考，考研中也常常出現(xiàn)快速排序的身影
2021-11-11
并發(fā)編程之Java內(nèi)存模型
這篇文章主要介紹了Java并發(fā)編程之內(nèi)存模型，Java內(nèi)存模型中的順序一致性，主要介紹重排序與順序一致性內(nèi)存模型，下面文章將圍繞Java內(nèi)存模型展開內(nèi)容，需要的小伙伴可以參考一下
2021-11-11
springcloud之Feign、ribbon如何設(shè)置超時時間和重試機(jī)制
這篇文章主要介紹了springcloud之Feign、ribbon如何設(shè)置超時時間和重試機(jī)制，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2021-08-08
Java泛型變量如何添加約束
這篇文章主要介紹了Java泛型變量如何添加約束,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
2020-05-05
springboot?集成activemq項目配置方法
這篇文章主要介紹了springboot?集成activemq項目配置方法,e-car項目配置通過引入activemq依賴,本文結(jié)合實例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧
2024-04-04
Java設(shè)計實現(xiàn)一個針對各種類型的緩存
這篇文章主要為大家詳細(xì)介紹了Java如何設(shè)計實現(xiàn)一個針對各種類型的緩存,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價值,感興趣的小伙伴可以了解一下
2023-11-11
將Java的List結(jié)構(gòu)通過GSON庫轉(zhuǎn)換為JSON的方法示例
GONS是Google在GitHub上開源的Java類庫,提供各種Java對象和JSON格式對象之間的轉(zhuǎn)換功能,將Java的List結(jié)構(gòu)通過GSON庫轉(zhuǎn)換為JSON的方法示例
2016-06-06
SpringBoot Mybatis批量插入Oracle數(shù)據(jù)庫數(shù)據(jù)
這篇文章主要介紹了SpringBoot Mybatis批量插入Oracle數(shù)據(jù)庫數(shù)據(jù)，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下
2022-08-08
Java連接MYSQL數(shù)據(jù)庫的詳細(xì)步驟
這篇文章主要為大家介紹了Java連接MYSQL數(shù)據(jù)庫的詳細(xì)步驟，感興趣的小伙伴們可以參考一下
2016-05-05
Java中的static靜態(tài)變量、靜態(tài)方法超詳細(xì)講解
Java中的static關(guān)鍵字用于表示靜態(tài)變量和靜態(tài)方法,靜態(tài)變量是類的成員變量,它們屬于類本身,而不是類的實例,這篇文章主要給大家介紹了關(guān)于Java中static靜態(tài)變量、靜態(tài)方法詳細(xì)講解的相關(guān)資料,需要的朋友可以參考下
2024-06-06