排序算法-7---希爾排序
概念
希爾排序（Shellsort）蒸殿，也稱遞減增量排序算法，是一種典型的插入排序算法，通過對原始序列進行分組進行排序终畅。希爾排序是非穩(wěn)定排序算法籍胯。
解題思路
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：
- 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高离福，即可以達到線性排序的效率
- 但插入排序一般來說是低效的杖狼，因為插入排序每次只能將數(shù)據(jù)移動一位
希爾排序的基本思想就是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時妖爷，再對全體記錄進行依次直接插入排序蝶涩。
矩陣的列數(shù)取決于步長序列(step sequence)
比如，如果步長序列為{1,5,19,41,109...}.. 就代表依次分成109列絮识、41列绿聘、 19列、 5列次舌、1列進行排序
不同的步長序列熄攘，執(zhí)行效率也不同
運行過程
1、選擇一個增量序列t1彼念，t2鲜屏，…，tk国拇，其中對于i>j洛史，有ti>tj，tk=1酱吝；（增量因子有多種取法也殖，最簡單的是t(i+1) = ti/2）
2、按增量序列個數(shù)k务热，對序列進行k 趟排序忆嗜；
3）每趟排序，根據(jù)對應(yīng)的增量ti崎岂，將待排序列分割成若干長度為m 的子序列捆毫，分別對各子表進行直接插入排序。僅增量因子為1 時冲甘，整個序列作為一個表來處理绩卤，表長度即為整個序列的長度。
-
例如：
希爾本人給出的步長序列是n/2k, 比如n為16時江醇，步長序列是{1, 2, 4, 8}
image
代碼
java
public void shell_sort(int[] arr) {
int gap = 1, i, j, len = arr.length;
int temp;
while (gap < len / 3)
gap = gap * 3 + 1;
for (; gap > 0; gap /= 3)
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}
性能
- 時間復(fù)雜度
**希爾排序的執(zhí)行時間依賴于增量序列濒憋。 **
希爾排序耗時的操作有：比較 + 后移賦值。
時間復(fù)雜度情況如下：（n指待排序序列長度）
- 最好情況：序列是正序排列陶夜，在這種情況下凛驮，需要進行的比較操作需（n-1）次。后移賦值操作為0次条辟。即O(n)
- 最壞情況：O(nlog2n)黔夭。
- 漸進時間復(fù)雜度（平均時間復(fù)雜度）：O(nlog2n)
希爾排序是按照不同步長對元素進行插入排序宏胯，當(dāng)剛開始元素很無序的時候，步長最大本姥，所以插入排序的元素個數(shù)很少胳嘲，速度很快；當(dāng)元素基本有序了扣草，步長很小了牛，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ猿矫睿柵判虻臅r間復(fù)雜度會比O(n2)好一些鹰祸。
希爾算法的性能與所選取的增量（分組長度）序列有很大關(guān)系。只對特定的待排序記錄序列密浑，可以準(zhǔn)確地估算比較次數(shù)和移動次數(shù)蛙婴。想要弄清比較次數(shù)和記錄移動次數(shù)與增量選擇之間的關(guān)系，并給出完整的數(shù)學(xué)分析尔破，至今仍然是數(shù)學(xué)難題街图。
希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時快速排序在最壞的情況下執(zhí)行的效率會非常差懒构。希爾排序沒有快速排序算法快餐济，因此中等大小規(guī)模表現(xiàn)良好，對規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇胆剧。
（注：專家們提倡絮姆，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快秩霍，再改成快速排序這樣更高級的排序算法篙悯。）
- 性能分析（穩(wěn)定性）
由于多次插入排序，我們知道一次插入排序是穩(wěn)定的铃绒，不會改變相同元素的相對順序鸽照，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動颠悬，最后其穩(wěn)定性就會被打亂矮燎，所以希爾排序是不穩(wěn)定的。
備注：希爾排序的時間性能優(yōu)于直接插入排序
參考文章
