【概述】

希爾排序是一種不穩定的排序方法，其是對直接插入排序的改進。

直接排序再基本本身基本有序時，只需要少量的插入操作，即可完成整個記錄的排序工作，所謂基本有序，就是小的關鍵字基本在前，大的關鍵字基本在后，但基本有序的條件十分苛刻，難以達到。

為了達到基本有序，采用跳躍分割策略，即將相距某個增量的記錄組成一個子序列，這樣保證子序列內分別進行直接插入排序得到的結果是基本有序而非局部有序。

而希爾排序的基本思想是：將整個待排序記錄序列分割成若干個子序列，在子序列內分別進行直接插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序。

【過程】

簡單來說，希爾排序就是在直接插入排序的基礎上，將直接插入排序中的 1 全部改變成增量 d 即可

實現步驟：

從第一個元素開始，該元素可以認為已經被排序選擇一個增量序列 t1,t2,…,tk，其中 ti>tj，tk=1

按增量序列個數 k，對序列進行 k 趟排序

每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序，僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度

? ? ? ? ? ? ? 宏觀排序

【時空復雜度分析】

希爾排序的時間復雜度分析是一個復雜的問題，其是所取增量的函數，在大量的實驗基礎上，可以得出，希爾排序的最優時間復雜度為 O(nlogn)，最差時間復雜度為 O(n^2)，當 n 在某個特定的范圍時，其時間性能約為 O(n^1.3)

而對于空間復雜度，其與直接插入相同，為 O(1)

【源程序】

void shellSort(int a[],int n){int d=0;//生成初始增量(分組數)dwhile(d<=n)d=3*d+1;while(d>=1){//循環的次數為增量縮小至1的次數for(int i=d;i<=n;i++){//循環的次數為第一個分組的第二個元素到數組的結束int temp=a[i];//暫存待插入關鍵碼，并設置哨兵int j=i-d;while(j>=1&&a[j]>temp){//尋找插入位置a[j+d]=a[j];//記錄后移d個位置j-=d;}if((j+d)!=i)//防止自我插入a[j+d]=temp;//插入記錄}d=(d-1)/3;//增量遞減} }

?

總結

以上是生活随笔為你收集整理的理论基础 —— 排序 —— 希尔排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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