希爾排序：通過比較相距一定間隔的元素來工作；各趟比較所用的距離（增量）隨著算法的進行而減小，直到只比較相鄰元素的最後一趟排序為止。是插入排序的一種，是針對直接插入排序算法的改進。
算法思想：先將要排序的序列按某個增量d分成若干個子序列，對每個子序列中全部元素分別進行直接插入排序，然後再用一個較小的增量對它進行分組，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。注意：增量的取值——一般的初次取序列的一半為增量，以後每次減半，直到增量為1。
算法實現代碼如下：
package exp_sort;
public class ShellSort {
public static void shell(int array[]) {
int j;
int average;
//設置增量的值
for (average = array.length / 2; average > 0; average /= 2) { //步長
for (int i = average; i < array.length; i++) { //子序列進行直接插入排序
int temp = array[i];
for (j = i; j >= average && temp < array[j - average]; j -= average) {
array[j] = array[j - average];
}
array[j] = temp;
}
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
shell(array);
}
}
算法分析：該算法是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對於有序的序列效率很高。所以，希爾排序的時間復雜度會比O(n^2)好一些，為O(n^1.5)，排序效率比插入排序高很多。由於多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，所以shell排序是不穩定的。希爾排序沒有快速排序算法快 O(N*(logN))，因此對中等大小規模的數據排序比較適用，對規模非常大的數據排序不是最優選擇。但是比O(N^2)復雜度的算法快得多。並且希爾排序非常容易實現，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞的情況下執行的效率會非常差。
