基本思想
先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
算法實現(xiàn)(Java語言)
package org.shirdrn.internal.sort;
/**
* <p><B>希爾排序算法類</B>
* <p>基本思想：
* <p>
* <p>先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的
* 倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插人排序；然后，取第二個增量d2<d1重復(fù)上
* 述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行
* 直接插入排序為止。
* <p>
* <p>該方法實質(zhì)上是一種分組插入方法。
*
* @author shirdrn
*
*/
public class ShellSort {
private Integer[] array;
public ShellSort(Integer[] array) {
this.array = array;
}
public void sort() {
int d = array.length;
do {
d /= 2;
shellPass(d); // 根據(jù)逐漸減小的間隔增量，循環(huán)調(diào)用一趟排序
}while(d>1);
}
/**
* 希爾一趟排序
*
* @param d 間隔增量
*/
private void shellPass(int d) {
Integer tmp;
for(int i=d; i<array.length; i++) { // 數(shù)組下標(biāo)從0開始，初始i=d表示一趟排序中第二個元素
tmp = array[i]; // array[i]的拷貝
// 如果待處理的無序區(qū)第一個元素array[i] < 有序區(qū)最大的元素array[i-d]
// 需要將有序區(qū)比array[i]大的元素向后移動
if(array[i]<array[i-d]) {
int j=i-d;
while(j>=0 && tmp<array[j]) {
array[j+d] = array[j]; // 將左側(cè)有序區(qū)中元素比array[i]大的array[j+d]后移
j -= d;
}
// 如果array[i] >= 左側(cè)有序區(qū)最大的array[i-d]，或者經(jīng)過掃描移動后，找到一個比array[i]小的元素
// 將右側(cè)無序區(qū)第一個元素tmp = array[i]放到正確的位置上
array[j+d] = tmp;
}
}
}
/**
* 輸出數(shù)組元素
*/
public String print() {
StringBuffer sb = new StringBuffer();
for(int i=0; i<array.length; i++) {
sb.append(array[i]);
if(i != array.length-1) {
sb.append(", ");
}
}
return sb.toString();
}
}
排序過程
希爾排序的過程如下：
首先初始化間隔d為待排序數(shù)組的長度，無需排序。
減小d，對于每次得到的間隔d，執(zhí)行多組排序，使得原始數(shù)組間隔為d的一個子數(shù)組為有序，該數(shù)組通過類似直接插入排序的算法來執(zhí)行排序。
直到，d減小為1的時候，整個數(shù)組為有序。這里，采用二分的策略來得到間隔d。
執(zhí)行希爾排序的過程示例如下：
假設(shè)待排序數(shù)組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數(shù)組大小為20。
首先，初始化d = 20。在循環(huán)中反復(fù)得到間隔d，根據(jù)d執(zhí)行一趟希爾排序。
對于d = 20/2 = 10：
根據(jù)d = 10來對數(shù)組排序，將原始數(shù)組分成2塊： {94,12,34,76,26,9,0,37,55,76}與{37,5,68,83,90,37,12,65,76,49}，也就是對如下數(shù)組分別進行直接插入排序：
{array[0],array[10]} = {94,37}
{array[1],array[11]} = {12,5}
{array[2],array[12]} = {34,68}
{array[3],array[13]} = {76,83}
{array[4],array[14]} = {26,90}
{array[5],array[15]} = {9,37}
{array[6],array[16]} = {0,12}
{array[7],array[17]} = {37,65}
{array[8],array[18]} = {55,76}
{array[9],array[19]} = {76,49}
第一趟希爾排序后，各個子數(shù)組變?yōu)椋?/p>
{37,5,34,76,26,9,0,37,55,49}與{94,12,68,83,90,37,12,65,76,76}，
即：array = {37,5,34,76,26,9,0,37,55,49,94,12,68,83,90,37,12,65,76,76}，
對于d = 10/2 = 5：
根據(jù)d = 5來對數(shù)組排序，將第一趟希爾排序后的數(shù)組分成4塊 ：{37,5,34,76,26}、{9,0,37,55,49}、{94,12,68,83,90}與{37,12,65,76,76}，也就是對如下數(shù)組分別進行直接插入排序：
{array[0],array[5],array[10],array[15]} = {37,9,94,37}
{array[1],array[6],array[11],array[16]} = {5,0,12,12}
{array[2],array[7],array[12],array[17]} = {34,37,68,65}
{array[3],array[8],array[13],array[18]} = {76,55,83,76}
{array[4],array[9],array[14],array[19]} = {26,49,90,76}
第二趟希爾排序后，各個子數(shù)組變?yōu)椋?/p>
{9,0,34,55,26}、{37,5,37,76,49}、{37,12,65,76,76}與{94,12,68,83,90}，
即：array = {9,0,34,55,26,37,5,37,76,49,37,12,65,76,76,94,12,68,83,90}。
對于d = 5/2 = 2：
根據(jù)d = 2來對數(shù)組排序，將第二趟希爾排序后的數(shù)組分成10塊： {9,0}、{34,55}、{26,37}、{5,37}、{76,49}、{37,12}、{65,76}、{76,94}、{12,68}與{83,90}，也就是對如下數(shù)組分別進行直接插入排序：
{array[0],array[2],array[4],array[6],array[8],array[10],array[12],array[14],array[16],array[18]} = {9,34,26,5,76,37,65,76,12,83}
{array[1],array[3],array[5],array[7],array[9],array[11],array[13],array[15],array[17],array[19]} = {0,55,37,37,49,12,76,94,68,90}
第三趟希爾排序后，各個子數(shù)組變?yōu)椋簕5,0}、{9,12}、{12,37}、{26,37}、{34,49}、{37,55}、{65,68}、{76,76}、{76,90}與{83,94}，
即：array = ：{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}。
對于d = 2/2 = 1：
根據(jù)d = 1來對數(shù)組排序，將第二趟希爾排序后的數(shù)組分成20塊：{5}、{0}、{9}、{12}、{12}、{37}、{26}、{37}、{34}、{49}、{37}、{55}、{65}、{68}、{76}、{76}、{76}、{90}、{83}、{94}，也就是對如下數(shù)組分別進行直接插入排序：
{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}
第四趟希爾排序以后，數(shù)組已經(jīng)有序：
array = {0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90,94}。
因為 d= 1，希爾排序結(jié)束。
測試用例
package org.shirdrn.internal.sort;
import junit.framework.TestCase;
public class TestShellSort extends TestCase {
private ShellSort sort;
private Integer[] array;
@Override
protected void setUp() throws Exception {
array = new Integer[]{
94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49
};
sort = new ShellSort(array);
}
public void testSort() {
// B(Before),A(After)
System.out.println("(B)Sorting : " + this.sort.print());
this.sort.sort();
System.out.println("(A)Sorting : " + this.sort.print());
}
}
測試結(jié)果：
(B)Sorting : 94, 12, 34, 76, 26, 9, 0, 37, 55, 76, 37, 5, 68, 83, 90, 37, 12, 65, 76, 49
(A)Sorting : 0, 5, 9, 12, 12, 26, 34, 37, 37, 37, 49, 55, 65, 68, 76, 76, 76, 83, 90, 94
算法分析
（一）時間復(fù)雜度
Shell排序的執(zhí)行時間依賴于增量序列。
好的增量序列的共同特征：
① 最后一個增量必須為1；
② 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。
有人通過大量的實驗，給出了目前較好的結(jié)果：當(dāng)n較大時，比較和移動的次數(shù)約在nl.25到1.6n1.25之間。
（二）空間復(fù)雜度
因為希爾排序依賴于增量序列，從而導(dǎo)致排序的趟數(shù)不固定，對于不同的增量執(zhí)行一趟希爾排序，只用到一個輔助變量。
（三）排序穩(wěn)定性
通過上述元素76可以看到，希爾排序不穩(wěn)定。
因此，希爾排序是不穩(wěn)定的。