图片化加手动推导深刻记忆希尔排序全过程

标签: 希尔排序

希尔排序原理:首先将待排序的元素分成多个子序列,使得每个子序列的元素个数相对较少,对各个子序列分别进行直接插入排序,最后在基本有序后最后做一次直接插入排序

时间复杂度:O(nlogn) 最坏是O(n ** s)(1<s<2) 不稳定的排序方法;

空间复杂度:O(1)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jul 18 03:42:18 2019

@author: honorwh
"""
#希尔排序
def ShellSort(A):
    count = len(A)
    step = count // 2
    while step > 0:
        for i in range(0, step):
            j = i + step
            while j < count:
                k = j - step
                key = A[j]
                while k >= 0:
                    if A[k] > key:
                        A[k + step] = A[k]
                        A[k] = key
                    k -= step
                j += step
        step //= 2
    return A
A = [3, 4, 2, 8, 9, 5, 1]
A = ShellSort(A)
print(A)

希尔排序有个重点是对于增量(increment)的选择,这里选择是step = len(A) // 2, step //= 2

结合以上图片给出每一步的数值转移:

A = [3, 4, 2, 8, 9, 5, 1]

3 4 2 8 9 5 1(以step = len(A) // 2为步长) 第一次比较的是3 8;8 1; 3 1

即3 4 2 8 9 5 1 --> 3 4 2 1 9 5 8 --> 1 4 2 3 9 5 8

所以,1 4 2 3 9 5 8是第一次比较的结果;同理,在以step = len(A) // 2的步长比较之后,step //= 2

即第二次(在本例已经是最后一次,因为step = 1),所以同理即可得到结果。

这个编辑比较麻烦,有兴趣可以自己每一步的详细过程推一推,更容易理解。

原文链接:加载失败,请重新获取