希爾排序 Shell’s Sort

我們都知道直接插入排序對有序度高的列表排序效率是比較高的。而當列表為倒序時，最后一位元素的值是最小的，直接插入排序會進行 n-1 次比較才能找到正確的位置。這種情況下直接插入排序的效率是很低的
希爾排序是改進的直接插入排序，也稱為縮小增量排序

希爾排序的基本思路：

把列表元素按下表的一定增量分組，對每組分別使用直接插入排序

這種做法成功的把大規模的有序度較低的數組轉換成了小規模的有序度高的數組，因此直接插入排序的效率提高了

實現：

希爾排序的思路就是將大數組轉化為小數組，分別插入排序后轉化為有序度相對較高的數組，再利用插入排序

希爾排序的本質還是插入排序，但是通過將數組巧妙分割，恰好利用了插入排序對小數組和有序度高的數組效率高的特點

public static void shellSort1(int[] arr) {int gap = arr.length / 2;System.out.println(Arrays.toString(arr));while (gap > 0) {for (int i = gap; i < arr.length; i++) {int j = i;int temp = arr[j];while (j - gap >= 0 && temp < arr[j - gap]) {// 移動arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}// 打印System.out.println(Arrays.toString(arr));gap /= 2;} }

時間復雜度：

希爾排序的時間復雜度和增量序列（即 gap 的大小）有關，因此非常復雜

例如 {1, 2, 4, 8, … }這個序列的最壞時間復雜度為 O(n)

{1, 3, 7, 2 (k)-1, … } 的最壞時間復雜度為 O(n^{1.5})

{1, 5, 19, 41, 109, … } 的最壞時間復雜度為 O(n^{1.3})

空間復雜度：

由于只用到了 1 個臨時變量，所以空間復雜度為O(1)

穩定性：

雖然插入排序是穩定的，但是希爾排序是多個插入排序交叉，所以可能破壞穩定性

相關章節
第一節 簡述
第二節 稀疏數組 Sparse Array
第三節 隊列 Queue
第四節 單鏈表 Single Linked List
第五節 雙向鏈表 Double Linked List
第六節 單向環形鏈表 Circular Linked List
第七節 棧 Stack
第八節 遞歸 Recursion
第九節 時間復雜度 Time Complexity
第十節 排序算法 Sort Algorithm
第十一節 冒泡排序 Bubble Sort
第十二節 選擇排序 Select Sort
第十三節 插入排序 Insertion Sort
第十四節 冒泡排序，選擇排序和插入排序的總結
第十五節 希爾排序 Shell’s Sort
第十六節 快速排序 Quick Sort
第十七節 歸并排序 Merge Sort

總結

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

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