快捷導(dǎo)航

如何利用Python動(dòng)態(tài)展示排序算法

更新時(shí)間：2021年10月14日 12:04:18 作者：微小冷

Python是一種簡(jiǎn)單易學(xué),功能強(qiáng)大的編程語言,它有高效率的高層數(shù)據(jù)結(jié)構(gòu),能夠簡(jiǎn)單、有效地實(shí)現(xiàn)面向?qū)ο缶幊?下面這篇文章主要給大家介紹了關(guān)于如何利用Python動(dòng)態(tài)展示排序算法的相關(guān)資料,需要的朋友可以參考下

前言

經(jīng)?？吹竭@種算法可視化的圖片，但往往做不到和畫圖的人心靈相通，所以想自己畫一下，本文主要實(shí)現(xiàn)歸并排序和希爾排序，如果想實(shí)現(xiàn)其他算法可參考這篇

C語言實(shí)現(xiàn)各種排序算法[選擇，冒泡，插入，歸并，希爾，快排，堆排序，計(jì)數(shù)]

選擇冒泡

這兩種排序方案簡(jiǎn)單到很難說是什么算法，其中選擇排序通過遍歷一次數(shù)組，選出其中最大（?。┑闹捣旁谛聰?shù)組的第一位,再從剩下的數(shù)里選出最大（?。┑?，放到第二位，依次類推；冒泡排序則是通過重復(fù)走訪要排序的數(shù)組，比較相鄰元素，如果順序不符合要求則交換位置，直到不需要交換為止。

選擇排序

冒泡排序

二者的核心代碼分別為：

#x為待排序列表，N=len(x)
#選擇排序
for i in range(N):
    iMax = i
    for j in range(i, N):
        if(x[j]>x[iMax]):
            iMax = j
    x[iMax],x[i] = x[i],x[iMax]

#冒泡排序
tempN = N-1
for i in range(tempN):
    for j in range(0, tempN-i):
        if(x[j]>x[j+1]):
            x[j],x[j+1] = x[j+1],x[j]

下面給出選擇排序的繪圖代碼，其他的所有排序算法，其實(shí)只需改變核心部分。

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation 

start,end,N = 10,100,9
x = np.random.randint(start, end, size=N)
Index = np.arange(N)
xs = []
nowIndex = []

for i in range(N):
    iMax = i
    for j in range(i, N):
        xs.append(x*1)      #存儲(chǔ)當(dāng)前順序，用于繪圖
        nowIndex.append([i,j,iMax]) #存儲(chǔ)當(dāng)前的i,j,max位置，用于繪圖
        if(x[j]>x[iMax]):
            iMax = j
            xs.append(x*1)
            nowIndex.append([i,j,iMax])
    x[iMax],x[i] = x[i],x[iMax]

fig, ax = plt.subplots()
colors = np.repeat('g',N)
colors[0] = 'b'
bar = ax.bar(Index,x,color=colors)

def animate(n):
    data = xs[n]
    colors = np.repeat('gray',N)
    colors[nowIndex[n]] = 'b','g','r'
    ax.clear()
    bar = ax.bar(Index, data, color=colors)
    return bar

ani = animation.FuncAnimation(fig, animate, 
    range(len(xs)), interval=500, repeat=False, blit=True)
plt.show()
ani.save("sort.gif")

插入排序

插入排序的基本思路是將數(shù)組分為前后兩個(gè)部分，前面有序，后面無序。逐個(gè)掃描無序數(shù)組，將每次掃描的數(shù)插入到有序數(shù)組中，從而有序數(shù)組越來越長(zhǎng)，無序數(shù)組越來越短，直到整個(gè)數(shù)組都是有序的。

核心代碼為

for i in range(1,N):
    j = i-1
    temp = x[i]
    while(x[i]<x[j] and j>=0):
        x[j+1] = x[j]
        j -= 1
    x[j+1] = temp

由于在這段代碼中，x[i]被取出放在旁邊，所以其動(dòng)態(tài)圖中大部分時(shí)間會(huì)缺失一個(gè)值，在圖中將其置于最右側(cè)，其動(dòng)態(tài)過程如圖所示，藍(lán)色表示抽出來準(zhǔn)備插進(jìn)去的那根bar

歸并排序

排序算法到這里才算有點(diǎn)意思，歸并排序是算法導(dǎo)論中介紹分治概念時(shí)提到的，基本思路是將數(shù)組拆分成子數(shù)組，然后令子數(shù)組有序，再令數(shù)組之間有序，從而整個(gè)數(shù)組有序。

算法步驟

設(shè)數(shù)組有 n個(gè)元素， { a 0 , a 1 , … , a n }

如果數(shù)組元素大于2，則將數(shù)組分成左數(shù)組和右數(shù)組，如果數(shù)組等于2，則將數(shù)組轉(zhuǎn)成有序數(shù)組
對(duì)左數(shù)組和右數(shù)組執(zhí)行1操作。
合并左數(shù)組和右數(shù)組。

可以發(fā)現(xiàn)，對(duì)長(zhǎng)度為 n 的數(shù)組，需要 log ₂ n 次的拆分，每個(gè)拆分層級(jí)都有 O ( n ) 的時(shí)間復(fù)雜度和 O ( n )的空間復(fù)雜度，所以其時(shí)間復(fù)雜度和空間復(fù)雜度分別為 O ( n log ₂ n ) 和 O ( n ) 。

其核心算法為

def Merge(X, Y):
    nL,nR = len(X), len(Y)
    iterL,iterR = 0,0
    xNew = []
    for _ in range(nL+nR):
        if(iterL==nL): return xNew + Y[iterR:]
        if(iterR==nR): return xNew + X[iterL:]
        if(X[iterL]<Y[iterR]):
            xNew.append(X[iterL])
            iterL += 1
        else:
            xNew.append(Y[iterR])
            iterR += 1
    return xNew

def MergeSort(x):
    if len(x)==1:
        return x
    if len(x)==2:
        return x if x[0]<x[1] else [x[1],x[0]]
    nL = len(x)//2
    return Merge(MergeSort(x[:nL]),
                 MergeSort(x[nL:]))

當(dāng)然這么寫效率是非常低的，如果像高效還是得用指針，但我都已經(jīng)用Python了，所以就不去想效率的問題，問題的關(guān)鍵是這種帶有返回值的遞歸程序根本沒法畫圖啊。。。所以還是改成指針的寫法

def Merge(X, nL):
    nR = len(X)-nL
    XL,XR = X[:nL]*1,X[nL:]*1
    iterL,iterR = 0,0
    for i in range(nL+nR):
        if(iterL==nL): break
        if(iterR==nR): 
            X[i:] = XL[iterL:]
            return
        if(XL[iterL]<XR[iterR]):
            X[i] = XL[iterL]
            iterL += 1
        else:
            X[i] = XR[iterR]
            iterR += 1

def MergeSort(X):
    if len(X)<2:
        return
    nL = len(X)//2
    MergeSort(X[:nL])
    MergeSort(X[nL:])
    Merge(X,nL)

這個(gè)圖。。怎么說呢，因?yàn)樵贛erge過程中，有很多bar被掩蓋掉了，所以可能只有畫圖的人能看懂吧。。。

希爾排序

據(jù)說是第一個(gè)突破 O ( n ² ) 的排序算法，又稱為縮小增量排序，本質(zhì)上也是一種分治方案。

在歸并排序中，先將長(zhǎng)度為n的數(shù)組劃分為nL和nR兩部分，然后繼續(xù)劃分，直到每個(gè)數(shù)組的長(zhǎng)度不大于2，再對(duì)每個(gè)不大于2的數(shù)組進(jìn)行排序。這樣，每個(gè)子數(shù)組內(nèi)部有序而整體無序，然后將有序的數(shù)組進(jìn)行回溯重組，直到重新變成長(zhǎng)度為n的數(shù)組為止。

希爾排序反其道而行之，在將數(shù)組劃分為nL和nR后，對(duì)nL和nR進(jìn)行按位排序，使得nL和nR內(nèi)部無序，但整體有序。然后再將數(shù)組進(jìn)行細(xì)分，當(dāng)數(shù)組長(zhǎng)度變成1的時(shí)候，內(nèi)部也就談不上無序了，而所有長(zhǎng)度為1的數(shù)組整體有序，也就是說有這些子數(shù)組所組成的數(shù)組是有序的。

算法步驟

設(shè)數(shù)組有 n 個(gè)元素， { a 0 , a 1 , … , a n }

如果數(shù)組元素大于2，則將數(shù)組分成左數(shù)組和右數(shù)組，并對(duì)左數(shù)組和右數(shù)組的元素進(jìn)行一對(duì)一地排序。
對(duì)每一個(gè)數(shù)組進(jìn)行細(xì)分，然后將每個(gè)子數(shù)組進(jìn)行一對(duì)一排序。

def ShellSort(arr):
    n = len(arr)
    nSub = n//2
    while nSub>0:
        for i in range(nSub,n):
            temp = arr[i]
            j = i-nSub
            while j>=0 and temp<arr[j]:
                arr[j+nSub] = arr[j]
                j -= nSub
            arr[j+nSub] = temp
        nSub //= 2