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

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

下面給出選擇排序的繪圖代碼，其他的所有排序算法，其實(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)#存儲當(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)圖中大部分時(shí)間會缺失一個值，在圖中將其置于最右側(cè)，其動態(tài)過程如圖所示，藍(lán)色表示抽出來準(zhǔn)備插進(jìn)去的那根bar

歸并排序

排序算法到這里才算有點(diǎn)意思，歸并排序是算法導(dǎo)論中介紹分治概念時(shí)提到的，基本思路是將數(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 ₂ n 次的拆分，每個拆分層級都有 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)

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

希爾排序

據(jù)說是第一個突破 O ( n ² ) 的排序算法，又稱為縮小增量排序，本質(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的時(shí)候，內(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)文章希望大家以后多多支持本站！

版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非www.sddonglingsh.com所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。