[TOC] ## 概述 希爾排序(Shell Sort)是**插入排序的**一種，它是針對直接插入排序算法的改進。 希爾排序又稱縮小增量排序，因 DL.Shell 于 1959 年提出而得名。 它通過比較相距一定間隔的元素來進行，各趟比較所用的距離隨著算法的進行而減小，直到只比較相鄰元素的最后一趟排序為止。 * 希爾排序時間復雜度是 `O(n^(1.3-2))`，空間復雜度為常數階 `O(1)`。 * 希爾排序沒有時間復雜度為 `O(n(logn))` 的快速排序算法快 ，因此對中等大小規模表現良好，但對規模非常大的數據排序不是最優選擇，總之比一般 `O(n^2 )` 復雜度的算法快得多。