使用Java實現希爾排序算法的簡單示例
更新時間：2016年05月04日 17:19:02 作者：apei830
這篇文章主要介紹了使用Java實現希爾排序算法的簡單示例,希爾排序可以被看作是插入排序的一種更高效的改進版本,需要的朋友可以參考下
簡介
希爾排序(縮小增量法) 屬于插入類排序,由Shell提出，希爾排序對直接插入排序進行了簡單的改進：它通過加大插入排序中元素之間的間隔，并在這些有間隔的元素中進行插入排序，從而使數據項大跨度地移動，當這些數據項排過一趟序之后，希爾排序算法減小數據項的間隔再進行排序，依次進行下去，進行這些排序時的數據項之間的間隔被稱為增量，習慣上用字母h來表示這個增量。
常用的h序列由Knuth提出，該序列從1開始，通過如下公式產生：
h = 3 * h +1
反過來程序需要反向計算h序列，應該使用
h=(h-1)/3
代碼實現
實現代碼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
}
實現代碼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ā)現其與直接插入排序的差別在于：直接插入排序中的h會以1代替。
Shell排序是不穩(wěn)定的，它的空間開銷也是O(1),時間開銷估計在O(N3/2)~O(N7/6)之間。
相關文章
自帶IDEA插件的阿里開源診斷神器Arthas線上項目BUG調試
這篇文章主要為大家介紹了自帶IDEA插件阿里開源診斷神器Arthas線上項目BUG調試，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-06-06
SpringMVC @GetMapping注解路徑沖突問題解決
MD5對密碼進行加密存儲是常見的一種加密方式，本文主要介紹了Java雙重MD5加密實現安全登錄，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
這篇文章主要介紹了Java實現常見的排序算法代碼實例,按照思路實現了以下幾個排序算法(冒泡排序、直接插入排序、直接選擇排序、快速排序),方便日后用到,特此記錄一下,需要的朋友可以參考下2023-11-11
這篇文章主要給大家介紹了關于JavaSE、JavaEE和JavaWeb三大工程目錄的相關資料,很多對java不是很了解的同學在看到課程?綱的時候發(fā)現??出現了JavaSE、JavaEE、JavaME、JavaWEB這些詞,搞得?頭霧?,需要的朋友可以參考下2023-07-07
這篇文章主要介紹了java控制線程運行,需要的朋友可以參考下2014-04-04
這篇文章主要介紹了Java 生成隨機驗證碼圖片的示例，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下2020-10-10
下面小編就為大家分享一篇基于Java數組實現循環(huán)隊列的兩種方法小結，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12
Java壓縮解壓zip技術_動力節(jié)點Java學院整理
Java解壓縮zip - 多個文件(包括文件夾)，對多個文件和文件夾進行壓縮，對復雜的文件目錄進行解壓。壓縮方法使用的是可變參數，可以壓縮1到多個文件2017-05-05
這篇文章主要介紹了為什么阿里巴巴要求日期格式化時必須有使用y表示年，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-08-08
這篇文章主要介紹了Java多線程Condition接口原理介紹，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09