我用 Python 3分钟实现9种经典排序算法的可视化
導讀：最近在某網站上看到一個視頻，是關于排序算法的可視化的，看著挺有意思的，也特別喜感。
不知道作者是怎么做的，但是突然很想自己實現一遍，而且用python實現特別快，花了一天的時間，完成了這個項目。主要包括希爾排序（Shell Sort）、選擇排序（Selection Sort）、快速排序（Quick Sort）、歸并排序（Merge Sort）等九種排序。
作者：愛笑的眼睛
來源：戀習Python（ID：sldata2017）
▲6分鐘演示15種排序算法
下面具體講解以下實現的思路，大概需要解決的問題如下：
如何表示數組
如何得到隨機采樣數組，數組有無重復數據
如何實現排序算法
如何把數組可視化出來
01 如何表示數組
python提供了list類型，很方便可以表示C++中的數組。標準安裝的Python中用列表(list)保存一組值，可以用來當作數組使用，不過由于列表的元素可以是任何對象，因此列表中所保存的是對象的指針。這樣為了保存一個簡單的[1,2,3]，需要有3個指針和三個整數對象。
對于數值運算來說這種結構顯然比較浪費內存和CPU計算時間，再次就不詳細論述。
02 如何得到隨機采樣數組，數組有無重復數據
假設我希望數組長度是100，而且我希望數組的大小也是在[0,100)內，那么如何得到100個隨機的整數呢？可以用random庫。
示例代碼：
data?=?list(range(100))
data?=?random.choices(data,?k=100)
print(data)
[52,?33,?45,?33,?48,?25,?68,?28,?78,?23,?78,?35,?24,?44,?69,?88,?66,?29,?82,?77,?84,?12,?19,?10,?
27,?24,?57,?42,?71,?75,?25,?1,?77,?94,?44,?81,?86,?62,?25,?69,?97,?86,?56,?47,?31,?51,?40,?21,?41,?
21,?17,?56,?88,?41,?92,?46,?56,?80,?23,?70,?49,?96,?83,?54,?16,?36,?82,?24,?68,?60,?16,?98,?16,?81,
?10,?13,?11,?24,?68,?35,?56,?39,?23,?44,?6,?30,?3,?60,?56,?66,?38,?28,?47,?47,?25,?90,?89,?38,?68,?
21]
但是以上代碼有個問題，random.choices是對一個序列進行重復采樣，得到的數組存在重復數據，那如果不希望存在重復數據，而是希望進行無重復采樣，怎么辦？
可以用random.sample函數，示例代碼：
print(data)
[49,?28,?56,?28,?44,?62,?81,?25,?48,?33,?54,?38,?30,?16,?13,?19,?23,?56,?60,?66,?41,?24,?68,?68,
?77,?92,?78,?24,?66,?3,?80,?94,?78,?41,?84,?88,?21,?56,?25,?25,?75,?24,?38,?82,?31,?52,?23,?10,?
71,?40,?27,?46,?33,?35,?56,?51,?1,?23,?12,?25,?89,?16,?21,?21,?11,?42,?47,?44,?81,?35,?86,?88,?
29,?36,?77,?16,?39,?6,?57,?69,?96,?68,?24,?86,?97,?90,?69,?10,?68,?98,?56,?44,?83,?47,?70,?17,?
47,?82,?60,?45]
這樣就可以得到無重復采樣數據了。
03 如何實現排序算法
算法種類較多，就不一一舉例；再次就以希爾排序(Shell Sort)為例講講：
希爾排序的原理：希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
基礎的插入法排序是兩重循環，希爾排序是三重循環，最外面一重循環，控制增量gap，并逐步減少gap的值。二重循環從下標為gap的元素開始比較，依次逐個跨組處理。最后一重循環是對組內的元素進行插入法排序。
這樣進行排序的優點在于每次循環，整個序列的元素都將小元素的值逐步向前移動，數值比較大的值向后移動。
示例代碼：
def?ShellSort(ds):
????assert?isinstance(ds,?DataSeq),?"Type?Error"
????Length?=?ds.length
????D?=?Length//2
????while?D>0:
????????i=0
????????while?i<Length:
????????????tmp?=?ds.data[i]
????????????j=i
????????????while?j>=1?and?ds.data[j-D]>tmp:
????????????????ds.SetVal(j,?ds.data[j-D])
????????????????j-=D
????????????ds.SetVal(j,?tmp)
????????????i+=D
????????D//=2
if?__name__?==?"__main__":
????ds=DataSeq(64)
????ds.Visualize()
????ds.StartTimer()
????ShellSort(ds)
????ds.StopTimer()
????ds.SetTimeInterval(0)
????ds.Visualize()
04 如何把數組可視化出來
有了隨機數組初始化方法，再實現好排序函數，我們還差一步，就是把排序函數中每次移動數組后將數組可視化并輸出。
對數組進行可視化，很容易想到python的可視化工具matplotlib！但是在項目中我并沒有用matplotlib，而是用了numpy+opencv。
為什么不用matplotlib？
因為在排序過程中，每次修改數組，都希望能夠實時修改圖片并輸出，matplotlib確實很方便，但是matplotlib的效率實在是不高，而且每次修改數組前后的兩幅圖片其實是差不多的。如果用matplotlib，每次都是要重新繪制圖片，非常耗時！！！
所以考慮自己生成圖片，在每次修改數組后，只將圖片中改動的那兩列進行修改即可！這樣就比用matplotlib每次重新繪制圖片效率高得多！
數組中主要有兩種操作，一種是對某個idx賦值，一種是交換某兩個idx的值。
示例代碼：
????WHITE?=?(255,255,255)
????RED?=?(0,0,255)
????BLACK?=?(0,0,0)
????YELLOW?=?(0,127,255)
????def?__init__(self,?Length,?time_interval=1,?sort_title="Figure",?repeatition=False):
????????pass
????def?Getfigure(self):
????????_bar_width?=?5
????????figure?=?np.full((self.length*_bar_width,self.length*_bar_width,3),?255,dtype=np.uint8)
????????for?i?in?range(self.length):
????????????val?=?self.data[i]
????????????figure[-1-val*_bar_width:,?i*_bar_width:i*_bar_width+_bar_width]?=?self.GetColor(val,?self.length)
????????self._bar_width?=?_bar_width
????????self.figure?=?figure
????def?_set_figure(self,?idx,?val):
????????min_col?=?idx*self._bar_width
????????max_col?=?min_col+self._bar_width
????????min_row?=?-1-val*self._bar_width
????????self.figure[?:?,?min_col:max_col]?=?self.WHITE
????????self.figure[?min_row:?,?min_col:max_col]?=?self.GetColor(val,?self.length)
????def?SetVal(self,?idx,?val):
????????self.data[idx]?=?val
????????self._set_figure(idx,?val)
????????self.Visualize((idx,))
????def?Swap(self,?idx1,?idx2):
????????self.data[idx1],?self.data[idx2]?=?self.data[idx2],?self.data[idx1]
????????self._set_figure(idx1,?self.data[idx1])
????????self._set_figure(idx2,?self.data[idx2])
????????self.Visualize((idx1,?idx2))
附上一張效果圖：
附上源碼鏈接：
https://github.com/ZQPei/Sorting_Visualization
（覺得不錯，記得幫忙點個star哦）
據統計，99%的大咖都完成了這個神操作
▼
更多精彩
在公眾號后臺對話框輸入以下關鍵詞
查看更多優質內容！
PPT?|?報告?|?讀書?|?書單?|?干貨?
大數據?|?揭秘?|?Python?|?可視化
人工智能?|?機器學習?|?深度學習?|?神經網絡
AI?|?1024?|?段子?|?區塊鏈?|?數學
猜你想看
怎樣教一臺計算機區分貓和狗？一文零基礎入坑機器學習
什么是數據湖？有什么用？終于有人講明白了……
10本書，從Python爬蟲小白進階數據分析大神（建議收藏）
猿宵節正確打開方式：你要的大數據、機器學習、神經網絡…已配齊
Q:?你都在用哪些排序算法？
歡迎留言與大家分享
覺得不錯，請把這篇文章分享給你的朋友
轉載 / 投稿請聯系：baiyu@hzbook.com
更多精彩，請在后臺點擊“歷史文章”查看
總結
以上是生活随笔為你收集整理的我用 Python 3分钟实现9种经典排序算法的可视化的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 百亿身家中年男子告别房地产转行学Pyth
- 下一篇： 2007-2019中国城市竞争力排行榜T