python中如何进行希尔排序?

美女程序员鼓励师

如果问大家用于科学计算,属于插入类排序的缩小增量法是什么?你知道吗?其实是希尔排序法。 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。本文会向大家向大家介绍python中的希尔排序及其使用代码。

希尔排序

背景:插入排序在小规模数据、数据基本有序时效率较高

思想:将序列分为若干子序列进行插入排序,待序列基本有序时,对整体进行插入排序

代码:

# python实现希尔排序(插入排序的一种)

# 先宏观进行调整,在进行微观调整

 

def shellSort(lst, k, reverse=False):

    length = len(lst)

    dk = k # 设置一个增量dk

    while dk > 0:

        for i in range(dk, length):

            temp = lst[i]

            j = i

            while j >= dk and lst[j - dk] > temp:

                lst[j] = lst[j - dk]

                j -= dk

            lst[j] = temp

        dk = int(dk / 2)

    if reverse == False:

        return lst

    else:

        lst.reverse()

        return lst

输出:

test1 = [19, 21, 4, 6, 25, 3, 99, 67, 12]

test2 = [19, 21, 4, 6, 25, 3, 99, 67, 12]

data1 = shellSort(test1, 7)

data2 = shellSort(test2, 2, True)

print("从小到大:", data1)

print("从大到小:", data2)

希尔排序在最优时间复杂会根据步长序列的不同而不同,最坏时间复杂度是O(n^2),在操作过程中是不稳定的,要注意哦~


以上是 python中如何进行希尔排序? 的全部内容, 来源链接: utcz.com/z/541531.html

回到顶部