sort降序shell_排序之希尔排序(shell sort)
前言
本篇博客是在伍迷兄的博客基礎(chǔ)上進(jìn)行的，其博客地址點(diǎn)擊就可以進(jìn)去，里面好博客很多，我的排序算法都來(lái)自于此；一些數(shù)據(jù)結(jié)構(gòu)方面的概念我就不多闡述了，伍迷兄的博客中都有詳細(xì)講解，而我寫(xiě)這些博客只是記錄自己學(xué)習(xí)過(guò)程，加入了一些自己的理解，同時(shí)也希望給別人提供幫助。
前提故事
騷年在上次與博主進(jìn)行了直接插入排序的討論后，找到了博主，說(shuō)：“博主，對(duì)于直接插入排序，我有重大的發(fā)現(xiàn)”，博主想了想，就問(wèn)：“什么發(fā)現(xiàn)？”，騷年：“我發(fā)現(xiàn)了如下兩點(diǎn)”
1)當(dāng)序列的個(gè)數(shù)比較少時(shí)，直接插入排序效率高；這個(gè)好理解，個(gè)數(shù)比較少，那么插入的次數(shù)也就少了，博主就說(shuō)：“恩，這個(gè)發(fā)現(xiàn)不難，卻也需要細(xì)心”。
2)如果序列本身就是基本有序，那么直接插入排序效率高；博主：“嗯？”，騷年解釋道：“你看直接插入排序的核心代碼：”
for(int i=1; i=0&&arr[j]>arr[j+1]; j--){
swap(arr,j,j+1);
}
}
騷年接著道：“如果序列有序，那么j>=0&&arr[j]>arr[j+1]條件就是不滿足的，插入操作就不會(huì)執(zhí)行，效率自然就高了?！?/p>
博主：“然后了？”。
騷年：“那么我們是不是可以在這兩點(diǎn)上做點(diǎn)事，來(lái)提高直接插入排序在普通序列上的效率了？”。
上述兩個(gè)條件過(guò)于苛刻，現(xiàn)實(shí)中記錄少或者基本有序都屬于特殊情，有條件當(dāng)然是好，條件不存在，我們創(chuàng)造條件，也是可以去做的；騷年與博主進(jìn)行了研究與討論，我們可以對(duì)序列進(jìn)行分組，分割成若干個(gè)子序列，然后對(duì)每個(gè)子序列分別進(jìn)行直接插入排序，當(dāng)整個(gè)序列都基本有序時(shí)，注意只是基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。
此時(shí)一定有人開(kāi)始疑惑了。這不對(duì)呀，比如我們現(xiàn)在有序列是{5,3,7,9,1,6,4,8,2}，現(xiàn)在將它分成三組，{5,3,7}， {9,1,6}，{4,8,2}，哪怕將它們各自排序排好了，變成{3,5,7}，{1,6,9}，{2,4,8}，再合并它們成 {3,5,7,1,6,9,2,4,8}，此時(shí)，這個(gè)序列還是雜亂無(wú)序，談不上基本有序，要排序還是重來(lái)一遍直接插入有序，這樣做有用嗎？需要強(qiáng)調(diào)一下， 所謂的基本有序，就是小的關(guān)鍵字基本在前面，大的基本在后面，不大不小的基本在中間，像{2,1,3,6,4,7,5,8,9}這樣可以稱為基本有序了。 但像{3,5,7,1,6,9,2,4,8}這樣的7在第三位，2在倒數(shù)第三位就談不上基本有序。
那么問(wèn)題就來(lái)了，我們分割待排序記錄的目的是減少待排序記錄的個(gè)數(shù)，并使整個(gè)序列向基本有序發(fā)展。而如上面這樣分完組后，就各自排序的方法達(dá)不到我們的要求。因此，我們需要采取跳躍分割的策略：將相距某個(gè)“增量”的記錄組成一個(gè)子序列，這樣才能保證在子序列內(nèi)分別進(jìn)行直接插入排序后得到的結(jié)果是基本有序而不是局部有序。
基本思想
將整個(gè)序列按照相距某個(gè)“增量”進(jìn)行拆分，然后逐個(gè)對(duì)子序列進(jìn)行直接插入排序，使得得到的結(jié)果基本有序，最后對(duì)基本有序的序列進(jìn)行一次直接插入排序，使得整個(gè)序列有序
代碼實(shí)現(xiàn)
java實(shí)現(xiàn)
/*** 希爾排序
*@paramarr 目標(biāo)序列*/
public static void shellSort(int[] arr){int len =arr.length;for(int gap=len/2; gap>=1; gap=gap/2){ //拆分整個(gè)序列，元素間距為gap(也就是增量)//對(duì)子序列進(jìn)行直接插入排序
for(int i=gap+1; i=0&&arr[j]>arr[j+gap]; j=j-gap){
swap(arr,j,j+gap);
}
}
}
}
View Code
執(zhí)行過(guò)程模擬
1)程序開(kāi)始執(zhí)行，初始序列為{5,3,7,9,1,6,4,8,2}，如下圖：
2)初始gap=len/2=4
2.1)i=gap=4，初始j=0；比較arr[j]與arr[j+gap],即arr[0]與arr[4],如下圖：
j=j-gap=-4，跳出，i++，i=5
2.2)i=5，j=i-gap=1，arr[1]=3 < arr[5]=6,不交換數(shù)據(jù)，如下圖：
j=j-gap=-3,跳出，i++,i=6
2.3)同理，當(dāng)i=6，7時(shí)，序列如下圖：
2.4)當(dāng)i=8時(shí)，序列如下：
那么gap=4時(shí)，最終序列為
3)gap=gap/2=2
3.1)i=gap=2,j=i-gap=0,arr[0]=1 < arr[2]=4不交換，j=j-gap=-2，i++，此時(shí)序列為：
3.2)i=3，j=i-gap=1，arr[1]=3 < arr[3]=8,不交換，j=j-gap=-1，i++,此時(shí)序列為：
3.3)同理，i=4時(shí)：
3.4)i=5時(shí)：
3.5)i=6時(shí)：
3.6)i=7時(shí)：
3.7)i=8時(shí)：
4)gap=gap/2=1，此時(shí)
for(int gap=len/2; gap>=1; gap=gap/2){ //拆分整個(gè)序列，元素間距為gap(也就是增量)//對(duì)子序列進(jìn)行直接插入排序
for(int i=gap; i=0&&arr[j]>arr[j+gap]; j=j-gap){
swap(arr,j,j+gap);
}
}
就是
//對(duì)子序列進(jìn)行直接插入排序
for(int i=1; i=0&&arr[j]>arr[j+1]; j=j-1){
swap(arr,j,j+1);
}
}
相信大家都發(fā)現(xiàn)了，上面代碼就是我們的直接插入排序，那么具體的模擬過(guò)程我也就不再贅述了，不懂的可以去看排序之直接插入排序
至此，整個(gè)序列就有序了。
難解之處
通過(guò)這段代碼的剖析，相信大家有些明白，希爾排序的關(guān)鍵并不是隨便的分組后各自排序，而是將相隔某個(gè)“增量”的記錄組成一個(gè)子序列，實(shí)現(xiàn)跳躍式的移動(dòng)，使得排序的效率提高。這里“增量”的選取就非常關(guān)鍵了，本例中是以gap=gap/2的方式選取增量的，可究竟應(yīng)該選取什么樣的 增量才是最好，目前還是一個(gè)數(shù)學(xué)難題，迄今為止還沒(méi)有人找到一種最好的增量序列。不過(guò)大量的研究表明，當(dāng)增量序列為dlta[k]=2t-k+1-1(0≤k≤t≤?log2(n+1)?)時(shí)，可以獲得不錯(cuò)的效率。需要注意的是，增量序列的最后一個(gè)增量值必須等于1才行。
總結(jié)
以上是生活随笔為你收集整理的sort降序shell_排序之希尔排序(shell sort)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 使用Visual Studio实现Win
- 下一篇： JAVA笔记（运算符）