前面幾個小節，我們分別介紹了冒泡排序，插入排序，直接快速排序 ，選擇排序本節，我們介紹插入排序的改進版的希爾排序。

希爾排序是1959年，Shell發明的，這是第一個突破O(n²)的排序算法，他與直接插入排序不同的是，他會優先比較距離較近的元素。因此，希爾排序又叫做縮小增量排序。

1、算法思想

其工作原理是定義一個間隔序列來表示排序過程中進行比較的元素之間有多遠的間隔，每次將具有相同間隔的數分為一組，進行插入排序，大部分場景中，間隔是可以提前定義好的，也可以動態生成。

希爾排序的實質就是分組的插入排序

2、優缺點

優點：
空間復雜度較好，O(1)；作為改進版的插入排序，是一種相對高效的基于交換元素的排序方法。
缺點：
(i) 不穩定，在交換的過程中，會改變元素的相對次序。
(ii) 希爾排序的時間復雜度依賴于增量序列函數，所以分析起來比較困難，當n在某個特定范圍的時候，希爾排序的時間復雜都約為O(n^1.3)

3、關鍵點

確定增量劃分序列組，在不同的組中進行直接插入排序。實際上每次都是在間隔為gap的距離中進行比較（根據下圖來理解）

4、圖例演示過程

最原始的那種增量，即從 gap=length/2 逐步減半，其實這還不算最快的希爾，有幾個增量在實踐中表現更出色，希爾排序是實現簡單但是分析極其困難的一個算法的例子。
說了這么多理論性的文字，可能不太好理解，所以用圖示來幫助大家更好的理解希爾排序和直接插入排序的關系。

給定一個數組 [55，2，6，4，32，12，9，73，26，37] 對其進行希爾排序的操作過程如下圖所示：

5、程序代碼c++

/**************************************************************************** @file Shell_sort.cpp* @author Shawn* @date 7 Jan 2019* @remark 7 Jan 2019* @theme Shell Sort***************************************************************************/ # include<iostream> using namespace std; void shellsort(int[], int);int main() {int array [] = {55,2,6,4,32,12,9,73,26,37};int len = sizeof(array) / sizeof(int);cout<<"輸入的原始序列: ";for(int i=0; i<len; i++) // 輸出原序列cout<<array[i]<<",";cout<<endl<<endl;cout<<" ----希爾排序開始---- " << endl;shellsort(array,len); // 調用排序函數return 0; }void shellsort(int a[], int size) {int i, j, gap;for (gap = size / 2; gap > 0; gap /= 2) // 每次的增量，遞減趨勢{for (i = gap; i < size; i++) //每次增量下，進行幾組插入排序，如第一步就是（從12，9，73，26，37）5次for (j = i ; j -gap >= 0 && a[j-gap] > a[j]; j -= gap)// 每個元素組中進行直接插入排序，看例子swap(a[j-gap], a[j]); //如果增量為2時他的插入查詢操作下標為：//（2-0，3-1/ 4-2-0，5-3-1/ 6-4-2-0，7-5-3-1/ 8-6-4-2-0，9-7-5-3-1）for(int k=0; k<size; k++) // 輸出每輪排序結果cout<<a[k]<<",";cout<<endl;} }

后記思考：

為什么希爾能突破O(n²)的界，可以用逆序數來理解，假設我們要從小到大排序，一個數組中取兩個元素如果前面比后面大，則為一個逆序，容易看出排序的本質就是消除逆序數，可以證明對于隨機數組，逆序數是O(n²)的，而如果采用“交換相鄰元素”的辦法來消除逆序，每次正好只消除一個，因此必須執行O(n²)的交換次數，這就是為什么冒泡、插入等算法只能到平方級別的原因，反過來，基于交換元素的排序要想突破這個下界，必須執行一些比較，交換相隔比較遠的元素，使得一次交換能消除多個逆序，希爾、快排、堆排等等算法都是交換比較遠的元素，只不過規則各不同罷了。 本段部分內容參考知乎冒泡的回答： https://www.zhihu.com/question/24637339/answer/84079774

下一講：堆排序

總結

以上是生活随笔為你收集整理的排序算法研究之希尔排序（shell sort）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。