欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

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

前言

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

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

選擇冒泡

這兩種排序方案簡單到很難說是什么算法,其中選擇排序通過遍歷一次數(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]

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

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)      #存儲當(dāng)前順序,用于繪圖
        nowIndex.append([i,j,iMax]) #存儲當(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ù)組分為前后兩個部分,前面有序,后面無序。逐個掃描無序數(shù)組,將每次掃描的數(shù)插入到有序數(shù)組中,從而有序數(shù)組越來越長,無序數(shù)組越來越短,直到整個數(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]被取出放在旁邊,所以其動態(tài)圖中大部分時間會缺失一個值,在圖中將其置于最右側(cè),其動態(tài)過程如圖所示,藍(lán)色表示抽出來準(zhǔn)備插進(jìn)去的那根bar

歸并排序

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

算法步驟

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

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

可以發(fā)現(xiàn),對長度為 n 的數(shù)組,需要 log 2 n 次的拆分,每個拆分層級都有 O ( n ) 的時間復(fù)雜度和 O ( n )的空間復(fù)雜度,所以其時間復(fù)雜度和空間復(fù)雜度分別為 O ( n log 2 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)

這個圖。。怎么說呢,因為在Merge過程中,有很多bar被掩蓋掉了,所以可能只有畫圖的人能看懂吧。。。

希爾排序

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

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

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

算法步驟

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

  1. 如果數(shù)組元素大于2,則將數(shù)組分成左數(shù)組和右數(shù)組,并對左數(shù)組和右數(shù)組的元素進(jìn)行一對一地排序。
  2. 對每一個數(shù)組進(jìn)行細(xì)分,然后將每個子數(shù)組進(jìn)行一對一排序。
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

總結(jié)

到此這篇關(guān)于如何利用Python動態(tài)展示排序算法的文章就介紹到這了,更多相關(guān)Python動態(tài)展示排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評論