使用Java實現(xiàn)希爾排序算法的簡單示例
更新時間：2016年05月04日 17:19:02 作者：apei830
這篇文章主要介紹了使用Java實現(xiàn)希爾排序算法的簡單示例,希爾排序可以被看作是插入排序的一種更高效的改進版本,需要的朋友可以參考下
簡介
希爾排序(縮小增量法) 屬于插入類排序,由Shell提出，希爾排序?qū)χ苯硬迦肱判蜻M行了簡單的改進：它通過加大插入排序中元素之間的間隔，并在這些有間隔的元素中進行插入排序，從而使數(shù)據(jù)項大跨度地移動，當這些數(shù)據(jù)項排過一趟序之后，希爾排序算法減小數(shù)據(jù)項的間隔再進行排序，依次進行下去，進行這些排序時的數(shù)據(jù)項之間的間隔被稱為增量，習慣上用字母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){ //對每個增量進行一次排序
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)文章
快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用，再加上快速排序思想----分治法也確實實用，因此很多軟件公司的筆試面試，包括像騰訊，微軟等知名IT公司都喜歡考這個，還有大大小的程序方面的考試如軟考，考研中也常常出現(xiàn)快速排序的身影2021-11-11
這篇文章主要介紹了Java并發(fā)編程之內(nèi)存模型，Java內(nèi)存模型中的順序一致性，主要介紹重排序與順序一致性內(nèi)存模型，下面文章將圍繞Java內(nèi)存模型展開內(nèi)容，需要的小伙伴可以參考一下2021-11-11
springcloud之Feign、ribbon如何設(shè)置超時時間和重試機制
這篇文章主要介紹了springcloud之Feign、ribbon如何設(shè)置超時時間和重試機制，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要介紹了Java泛型變量如何添加約束,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05
這篇文章主要介紹了springboot?集成activemq項目配置方法,e-car項目配置通過引入activemq依賴,本文結(jié)合實例代碼給大家介紹的非常詳細,感興趣的朋友跟隨小編一起看看吧2024-04-04
Java設(shè)計實現(xiàn)一個針對各種類型的緩存
這篇文章主要為大家詳細介紹了Java如何設(shè)計實現(xiàn)一個針對各種類型的緩存,文中的示例代碼講解詳細,具有一定的學習價值,感興趣的小伙伴可以了解一下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ù)，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
這篇文章主要為大家介紹了Java連接MYSQL數(shù)據(jù)庫的詳細步驟，感興趣的小伙伴們可以參考一下2016-05-05
Java中的static靜態(tài)變量、靜態(tài)方法超詳細講解
Java中的static關(guān)鍵字用于表示靜態(tài)變量和靜態(tài)方法,靜態(tài)變量是類的成員變量,它們屬于類本身,而不是類的實例,這篇文章主要給大家介紹了關(guān)于Java中static靜態(tài)變量、靜態(tài)方法詳細講解的相關(guān)資料,需要的朋友可以參考下2024-06-06