希爾排序（Shell Sort）是一種插入排序算法，因D.L.Shell于1959年提出而得名。
Shell排序又稱作縮小增量排序。
1、算法思想
先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然后，取第二個增量d21重復上述的分組和排序，直至所取的增量d?t=1(d?tt-l<…?21)，即所有記錄放在同一組中進行直接插入排序為止。
該方法實質上是一種分組插入方法。?
2、代碼實現
~~~
package sort;
/**
* 希爾排序ShellSoet
*
* 先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。
*
* 所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；
*
* 然后，取第二個增量d21重復上述的分組和排序，直至所取的增量d t=1(d tt-l<… 21)，即所有記錄放在同一組中進行直接插入排序為止。
*
* 該方法實質上是一種分組插入方法。
*
* @author yunhai
*/
public class ShellSort {
public static void main(String[] args) {
int source[] = new int[]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4, 6};
System.out.print("排序前：\t");
printArray(source);
shellSort(source);
System.out.print("排序后：\t");
printArray(source);
}
private static void shellSort(int[] source) {
int j;
for (int gap = source.length / 2; gap > 0; gap /= 2) { // gap 為增長序列，遞減至1【亦可自定義增長序列】
for (int i = gap; i < source.length; i++) { // 【直接插入排序】，從第一個gap處向后移,直至移到最后一個數
int temp = source[i];// 當前gap處的值
for (j = i; j >= gap && temp < source[j - gap];) {// 最后一個數如果是第一個gap的倍數，按理應第一次循環，但卻最后循環
source[j] = source[j - gap]; // 較大數往后移
j -= gap; // 亦可放在循環體內
}
source[j] = temp; // 跳出循環意味著temp的位置已確定
}
System.out.print("增長序列" + gap + ": ");
printArray(source);
}
}
private static void printArray(int[] source) {
for (int i = 0; i < source.length; i++) {
System.out.print(source[i] + ",");
}
System.out.println();
}
}
~~~
3、算法分析
1）、增量序列的選擇。
Shell排序的執行時間依賴于增量序列。好的增量序列的共同特征如下：
a.最后一個增量必須為1。
b.應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
有人通過大量實驗給出了目前最好的結果：當n較大時，比較和移動的次數大概在n^1.25到n^1.26之間。
2）、Shell排序的時間性能優于直接插入排序。
希爾排序的時間性能優于直接排序的原因如下：
a.當文件初態基本有序時，直接插入排序所需的比較和移動次數均較少。
b.當n值較小時，n和n^2的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度O(n^2)差別不大。
c.在希爾排序開始時增量較大，分組較多，每組記錄數目少，故每組內直接插入排序較快，后來增量d(i)逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按d(i-1)做為距離拍過序，使文件較接近于有序狀態，所以新的一趟排序過程也較快。因此，希爾排序在效率上較直接插入排序有較大的改進。
3）、穩定性
希爾排序是不穩定的。
4、算法改進
增量序列的選擇：Shell排序的執行時間依賴于增量序列。?
好的增量序列的共同特征：?
①?最后一個增量必須為1；?
② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
源碼地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/ShellSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/ShellSort.java)
