希爾排序，又稱為““縮小增量排序””，他的實質(zhì)是采用分組插入的方法，將整個數(shù)組分為幾組，從而減少插入排序的數(shù)據(jù)量，將每組的兩端的元素進(jìn)行比較，然后交換，然后縮小增量，即重新分組，經(jīng)過幾次縮小增量后，基本達(dá)到有序的情況，再對全體進(jìn)行一次直接插入排序。

代碼如下

public void shellInsertSort(int []a,int n) {int gap,i,j,tmp;for(gap = n/2;gap > 0;gap = gap/2) {for(i = gap;i < n;i++) {for(j = i-gap;j >= 0&&(a[j]>a[j+gap]);j = j-gap) {tmp = a[j];a[j] = a[j+gap];a[j+gap] = tmp;}}}for(i = 0;i < a.length;i++) {System.out.println(a[i]);}}

可以畫圖自己來理解消化

值得欣喜的是，希爾排序的時間復(fù)雜度不再是O(n2)，但這種跳躍的移動導(dǎo)致排序不穩(wěn)定，并且只能用于順序結(jié)構(gòu)，還有就是增量序列的選取，應(yīng)該使增量序列的值沒有除了1之外的公因子，而且最后的增量必須為1。最后，因為他的比較次數(shù)和移動次數(shù)都比直接插入排序要少，n比較大是，效果越好，所以適用于初始無序，n比較大的情況

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

總結(jié)

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

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