04.希尔排序

希尔排序 #

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. 希尔排序代码实现 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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)
本站总访问量  次  |  您是本站第  位访问者