???? 希爾排序是插入排序的一種類型，也可以用一個形象的叫法縮小增量法?；舅枷刖褪前岩粋€數(shù)組分為好幾個數(shù)組，有點像分治法，不過這里的劃分是用一個常量d來控制。

這個0<d<n,n為數(shù)組的長度。這個算法有了插入排序的速度，也可以算是一個改進算法，在插入算法中，如果有一個最小的數(shù)在數(shù)組的最后面，用插入算法就會重最后一個

位置移動到第一個，這樣就會浪費很大，使用這個改進的希爾排序可以實現(xiàn)數(shù)據(jù)元素的大跨度的移動。也就是這個算法的優(yōu)越之處。

???? 希爾排序算法的基本思想是：先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各 組內(nèi)進行直接插人排序；然后，取第二個增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…< d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。該方法實質(zhì)上是一種分組插入方法。?? ??

public static void ShellSort(int[] H) {
?? ??? ?int dk = 1;
?? ??? ?while (dk <= H.length / 3)
?? ??? ??? ?dk = dk * 3 + 1;????????????????????????? //確定增量的過程
?? ??? ?while (dk>= 1) {?????????????????????????????
?? ??? ??? ?for (int i = dk; i <= H.length - 1; i = i + dk) {???????? //直接插入法
??? ??? ??? ???? int x = H[i];
?? ??? ??? ??? ?int j = i - dk;???????????????????????????????
?? ??? ??? ??? ?for (; j >= 0&&x < H[j]; j = j - dk) {
?? ??? ??? ??? ??? ??? ?H[j + dk] = H[j];?????????????????????????? ? ? ? ?? //?? for (; j >= 0; j--) {if (x < H[j]) {H[j + 1] = H[j]; }? else break;}??? 對比一下，簡便方法
?? ??? ??? ??? ?}
?? ??? ??? ??? ?H[j + dk] = x;
?? ??? ??? ?}
?? ??? ??? ?dk = dk / 3;?????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? //縮小增量，到1的時候是直接插入法。
?? ??? ?}
?? ??? ?for (int k : H) {
?? ??? ??? ?System.out.print(k + " ");
?? ??? ?}? ????
?? ?}
?? ?public static void main(String[] args) {
?? ??? ?// TODO Auto-generated method stub
?? ??? ?int[] H = { 4,? 6, 3, 7, 21,? 14, 28, 24, 31, 33, 2 };
?? ??? ?ShellSort(H);
?? ?}

轉(zhuǎn)載于:https://www.cnblogs.com/neversayno/p/5058174.html

總結(jié)

以上是生活随笔為你收集整理的数据结构之shell排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。