希爾排序：
希爾排序，英文名Shell Sort,又被稱為縮小增量排序。無論是中文名，英文名，還是别名，都透露着一股學渣不可侵犯的“神聖”感。當初學習插入法的時候，一看到這麼接地氣的名字，學起來也有信心。但是看到希爾排序這高端大氣上檔次的名字，一下子就起了退避三舍的心思。那麼，希爾排序真的就這麼的拒人于千裡之外嗎？其實學會了希爾排序的思路後，就不覺得它有多難了。
希爾排序其實也是插入排序的一種，不過希爾排序是将序列按下标的一定增量分組，分别對每組序列使用直接插入排序算法排序，随着增量逐漸減少，每組包含的元素越來越多，當增量減至1時，整個序列恰被分成一組，再進行一次整個序列的直接插入排序，整個算法就此終止。
既然最終都是要使用直接插入排序對整個序列進行排序，那麼為什麼要用一個增量來把序列分組呢？這是因為直接插入排序在元素基本有序的情況下，效率是很高的，當通過分組完成插入排序，首先每一組的資料基數小了，是以使用直接插入的代價變小，同時，每完成一組序列的排序，整個序列就更趨于有序化，對于下一輪的插入排序來說，更加有序的序列代表着效率的進一步提高，是以相比排序算法：插入排序中介紹的直接插入排序算法，以及排序算法：二分法插入排序中介紹的二分法插入排序算法，希爾排序在時間效率上要快得多。
下面以長度為10的序列:{4，6，3，1，7，5，2，9，8，6}的希爾排序過程做示範：
首先求增量：10/2=5；
增量的目的是将序列按增量分組，增量為5意味着序列中的元素每隔5個是一組
這就将序列分成了5組，分别是：（相同顔色為一組）
4 6 3 1 7 5 2 9 8 6
即為{4，5}、{6，2}、{3，9}、{1，8}、{7，6}
（注：這裡的分組并不是将序列的元素拷貝出來放入新的序列，而隻是在原序列上用增量去邏輯上的劃分，其實從實體上來看，元素仍然存儲于原序列裡）
對這5個分組分别使用直接插入排序，結果如下：
4 2 3 1 6 5 6 9 8 7
（ps:可以看到兩個6之間的互相位置交換了，這證明希爾排序是不穩定的）
然後，縮小增量：5/2=2
對序列按增量2進行分組：
4 2 3 1 6 5 6 9 8 7
分别是{4，3，6，6，8}、{2，1，5，9，7}
對這兩個組分别使用直接插入排序，結果如下：
3 1 4 2 6 5 6 7 8 9
接下來再縮小增量：2/2=1
發現增量已經減小到1了，這代表将整個序列分為一組，也就相當于不分組。
對序列：
3 1 4 2 6 5 6 7 8 9
進行直接插入排序：
第一趟：[1] 3 4 2 6 5 6 7 8 9
第二趟：[1 3] 4 2 6 5 6 7 8 9
第三趟：[1 3 4] 2 6 5 6 7 8 9
第四趟：[1 2 3 4] 6 5 6 7 8 9
第五趟：[1 2 3 4 6] 5 6 7 8 9
第六趟：[1 2 3 4 5 6] 6 7 8 9
此時整個序列已經有序，以上就是一次完整的希爾排序過程。
本文根據上述的希爾排序思路思路給出C++與Java的代碼實作，并且使用Java對希爾排序算法和，二分法插入排序算法、插入排序算法、選擇排序算法，以及兩種冒泡排序算法進行性能比較。
C++代碼：
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void shellSort(int *arr, int length)
{
if (arr == NULL || length <= )return;
int d = length / ;
for (; d > ; d = d / )
{
for (int i = d; i < length; ++i)
{
for (int j = i - d; j >= ;j-=d)
if (arr[j]>arr[j + d])
{
swap(&arr[j], &arr[j + d]);
}
}
}
}
Java代碼：
private void shellSort(List<Integer> list) {
int length = list.size();
for (int gap = length / ; gap > ; gap /= ) {
for (int i = gap; i < length; ++i) {
int temp = list.get(i);
int j = i - gap;
while (j >= && list.get(j) > temp) {
list.set(j + gap, list.get(j));
j -= gap;
}
list.set(j + gap, temp);
}
}
}
使用完全相同的，元素為整數的List對上述幾種算法進行性能測試結果如下：
序列長度為1000：
序列長度為5000：
序列長度為10000：
序列長度為50000：
可以看出希爾排序的效率遠遠高于其他幾種排序算法。