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