概述
希爾(Shell)排序又稱為縮小增量排序不翩，它是一種插入排序。它是直接插入排序算法的一種威力加強(qiáng)版麻裳。
代碼實(shí)現(xiàn)
/**
* 基本思想：
* 先取一個小于n的整數(shù)d1作為第一個增量口蝠，把文件的全部記錄分組。
* 所有距離為d1的倍數(shù)的記錄放在同一個組中津坑。
* 先在各組內(nèi)進(jìn)行直接插入排序妙蔗；然后，取第二個增量d2<d1
* 重復(fù)上述的分組和排序疆瑰，直至所取的增量 =1( < …<d2<d1)灭必，
* 即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂? *
*
*
*
* @author yeoggc
*
*/
public class 希爾排序 {
private void shellSort(int[] array) {
int gap = array.length / 2;// 初始化gap為數(shù)組長度/2
while (1 <= gap) {// 中止條件是gap<1
// 對步長為gap的元素進(jìn)行分組
// 交替的對每組進(jìn)行直接插入排序
for (int i = gap; i < array.length; i++) {
int temp = array[i];// 待排序的數(shù)據(jù)
int j = 0;// 有序區(qū)中待比較元素的下標(biāo)，初始時乃摹，從有序區(qū)中最后一個元素開始比較起
// 對步長為 gap 的元素組進(jìn)行排序
for (j = i - gap; j >= 0 && temp < array[j]; j = j - gap) {
array[j + gap] = array[j];
}
array[j + gap] = temp;
}
System.out.format("gap = %d:\t", gap);
printAll(array);
gap = gap / 2; // 減小增量
}
}
public static void main(String[] args) {
int[] array = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
// 調(diào)用希爾排序方法
希爾排序 shell = new 希爾排序();
System.out.print("排序前:\t\t");
shell.printAll(array);
shell.shellSort(array);
System.out.print("排序后:\t\t");
shell.printAll(array);
}
// 打印完整序列
public void printAll(int[] list) {
for (int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
}
算法分析
這例子希爾排序的步長選擇都是從n/2開始禁漓，每次再減半，直到最后為1孵睬。這并不是最高效的步長選擇播歼。
希爾排序是不穩(wěn)定的：我們知道一次插入排序是穩(wěn)定的，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動秘狞，最后其穩(wěn)定性就會被打亂叭莫，即希爾排序中相等數(shù)據(jù)可能會交換位置。
希爾排序的平均時間復(fù)雜度為O(nlog2n)烁试。
直接插入排序和希爾排序的比較
直接插入排序是穩(wěn)定的雇初；而希爾排序是不穩(wěn)定的。
直接插入排序更適合于原始記錄基本有序的集合减响。
希爾排序的比較次數(shù)和移動次數(shù)都要比直接插入排序少靖诗，當(dāng)N越大時，效果越明顯支示。
在希爾排序中刊橘，增量序列g(shù)ap的取法必須滿足：最后一個步長必須是 1 。
直接插入排序也適用于鏈?zhǔn)酱鎯Y(jié)構(gòu)颂鸿；希爾排序不適用于鏈?zhǔn)浇Y(jié)構(gòu)促绵。
