04.Array-Shell-Sort.md

1. 希尔排序算法思想

希尔排序（Shell Sort）基本思想：

将整个序列切按照一定的间隔取值划分为若干个子序列，每个子序列分别进行插入排序。然后逐渐缩小间隔进行下一轮划分子序列和插入排序。直至最后一轮排序间隔为 1，对整个序列进行插入排序。

2. 希尔排序算法步骤

• 首先确定一个元素间隔数 gap，然后将参加排序的序列按此间隔数从第 1 个元素开始一次分成若干个子序列，即分别将所有位置相隔为 gap 的元素视为一个子序列，在各个子序列中采用某种排序方法进行插入排序。
• 然后减少间隔数，并重新将整个序列按新的间隔数分成若干个子序列，再分别对各个子序列进行排序，如此下去，直到间隔数 gap = 1。

3. 希尔排序图解演示

4. 希尔排序算法分析

• 希尔排序方法的速度是一系列间隔数 $gap_i$ 的函数，不太容易弄清楚比较次数与 gap 之间的依赖关系，并给出完整的数学分析。
• 上面算法中，由于采用 $gap_i = \lfloor gap_{i-1}/2 \rfloor$ 的方法缩小间隔数，对于具有 n 个元素的序列，若 $gap_1 = \lfloor n/2 \rfloor$，则经过 $p = \lfloor log_2 n \rfloor$ 趟排序后就有 $gap_p = 1$，因此，希尔排序方法的排序总躺数为 $\lfloor log_2 n \rfloor$。
• 从算法中也可以看到，最外层的 while 循环为 $log_2 n$ 数量级，中间层 do-while 循环为 n 数量级。当子序列分得越多时，子序列内的元素就越少，最内层的 for 循环的次数也就越少；反之，当所分的子序列个数减少时，子序列内的元素也随之增多，但整个序列也逐步接近有序，而循环次数却不会随之增加。因此，希尔排序算法的时间复杂度在 $O(n log_2 n)$ 与 $O(n^2)$ 之间。
• 希尔排序方法是一种不稳定排序算法。

5. 希尔排序代码实现

class Solution:
    def shellSort(self, arr):
        size = len(arr)
        gap = size // 2

        while gap > 0:
            for i in range(gap, size):
                temp = arr[i]
                j = i
                while j >= gap and arr[j - gap] > temp:
                    arr[j] = arr[j - gap]
                    j -= gap
                arr[j] = temp
            gap = gap // 2
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.shellSort(nums)