過細解讀希爾排序算法與相干的Java代碼完成。本站提示廣大學習愛好者：（過細解讀希爾排序算法與相干的Java代碼完成）文章只能為提供參考，不一定能成為您想要的結果。以下是過細解讀希爾排序算法與相干的Java代碼完成正文
希爾排序（Shell's sort）是一種異常“奇異”的排序算法。說它“奇異”，是由於沒有任何人能清晰地解釋它的機能究竟能到甚麼情形。希爾排序因DL．Shell於1959年提出而得名。自從C. A. R. Hoare在1962年提出疾速排序後，因為其更加簡略，普通采取疾速排序。然則，很多數學家們照樣孳孳不倦地尋覓希爾排序的最好龐雜度。作為通俗法式員，我們可以進修下希爾的思緒。
趁便說一句，在希爾排序湧現之前，盤算機界廣泛存在“排序算法弗成能沖破O(n2)”的不雅點。希爾排序的湧現打破了這個魔咒，很快，疾速排序等算法接踵問世。從這個意義上說，希爾排序率領我們走向了一個新的時期。
算法概述/思緒
希爾排序的提出，重要基於以下兩點：
1.拔出排序算法在數組根本有序的情形下，可以近似到達O(n)龐雜度，效力極高。
2.但拔出排序每次只能將數據挪動一名，在數組較年夜且根本無序的情形下機能會敏捷好轉。
基於此，我們可使用一種分組的拔出排序辦法，詳細做法是：（以一個16元素年夜小的數組為例）
1.選擇一個增量delta，該增量年夜於1，從數組中按此增量選擇出子數組停止一次直接拔出排序。例如，若選擇增量為5，則對下標為0，5，10，15的元素停止排序。
2.保存該增量delta並順次挪動首個元素停止直接拔出排序，直到一輪完成。關於下面的例子，則順次對數組[1，6，11]，[2，7，12]，[3，8，13]，[4，9，14]停止排序。
3.減小增量，赓續反復上述進程，直到增量減小為1.明顯，最初一次為直接拔出排序。
4.排序完成。
從下面可以看出，增量是赓續減小的，是以，希爾排序又被成為“減少增量排序”。
代碼完成
package sort;
public class ShellSortTest {
public static int count = 0;
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data);
shellSort(data);
print(data);
}
public static void shellSort(int[] data) {
// 盤算出最年夜的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (int i = h; i < data.length; i += h) {
if (data[i] < data[i - h]) {
int tmp = data[i];
int j = i - h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
print(data);
}
}
// 盤算出下一個h值
h = (h - 1) / 3;
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}
運轉成果：
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 9 8 7 1 2 3 4 5 6 8 9 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
算法機能/龐雜度
希爾排序的增量數列可以任取，須要的獨一前提是最初一個必定為1（由於要包管按1有序）。然則，分歧的數列拔取會對算法的機能形成極年夜的影響。下面的代碼演示了兩種增量。
切記：增量序列中每兩個元素最好不要湧現1之外的公因子！（很明顯，按4有序的數列再去按2排序意義其實不年夜）。
上面是一些罕見的增量序列。
第一種增量是最後Donald Shell提出的增量，即折半下降直到1。據研討，應用希爾增量，當時間龐雜度照樣O(n2)。
第二種增量Hibbard：{1, 3, ..., 2^k-1}。該增量序列的時光龐雜度年夜約是O(n^1.5)。
第三種增量Sedgewick增量：(1, 5, 19, 41, 109,...)，其生成序列或許是9*4^i - 9*2^i + 1或許是4^i - 3*2^i + 1。
算法穩固性
我們都曉得拔出排序是穩固算法。然則，Shell排序是一個屢次拔出的進程。在一次拔出中我們能確保不挪動雷同元素的次序，但在屢次的拔出中，雷同元素完整有能夠在分歧的拔出輪次被挪動，最初穩固性被損壞，是以，Shell排序不是一個穩固的算法。
算法實用場景
Shell排序固然快，然則究竟是拔出排序，其數目級並沒有後起之秀--疾速排序O(n㏒n)快。在年夜量數據眼前，Shell排序不是一個好的算法。然則，中小型范圍的數據完整可使用它。
