python中進(jìn)行希爾排序的方法

這篇文章將為大家詳細(xì)講解有關(guān)python中進(jìn)行希爾排序的方法，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

 希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，是將整個(gè)無(wú)序列分割成若干小的子序列分別進(jìn)行插入排序的方法。它是簡(jiǎn)單插入排序經(jīng)過(guò)改進(jìn)之后的一個(gè)更高效的版本，也稱為縮小增量排序，同時(shí)該算法是沖破O(n2）的第一批算法之一。

希爾排序

背景：插入排序在小規(guī)模數(shù)據(jù)、數(shù)據(jù)基本有序時(shí)效率較高

思想：將序列分為若干子序列進(jìn)行插入排序，待序列基本有序時(shí)，對(duì)整體進(jìn)行插入排序

代碼：

# python實(shí)現(xiàn)希爾排序(插入排序的一種)
# 先宏觀進(jìn)行調(diào)整，在進(jìn)行微觀調(diào)整
 
def shellSort(lst, k, reverse=False):
    length = len(lst)
    dk = k # 設(shè)置一個(gè)增量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)

關(guān)于python中進(jìn)行希爾排序的方法就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。