欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 17:50:32
...

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

时间复杂度: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),所以同理即可得到结果。

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

相关标签: 希尔排序