本文通過動態(tài)可視化圖來解析快速排序法和計數(shù)排序法。
這幾天“手機殼顏色換主題色”需求引起一波轟動，關(guān)于事情真?zhèn)芜@里不做判斷。但技術(shù)仍然是實施手段，產(chǎn)品最終還是要靠技術(shù)來實現(xiàn)，產(chǎn)品還是不能遠(yuǎn)離技術(shù)。多理解一點技術(shù)知識，和開發(fā)大佬說話就多了一份硬氣。連基礎(chǔ)的排序算法都不懂的產(chǎn)品經(jīng)理很難的得到開發(fā)及項目組的青睞。
那么你花5分鐘閱讀，再花5分鐘理解。以后就可以在公司走路帶風(fēng)，抬頭挺胸。
關(guān)于“冒泡排序、插入及選擇排序”可以看之前一篇文章：走進開發(fā)，5分鐘熟悉3種經(jīng)典排序算法
一、快速排序法
快速排序是冒泡排序的改進版，整個過程就在拆拆補補，東拆西補或西拆東補，一邊拆一邊補，直到所有元素達(dá)到有序狀態(tài)。
1. 快速排序法基本思路
先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)，然后進行大小分區(qū)；
分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊；
再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)，排序完成。
下面先通過圖文形式一步一步進行拆解。
拿[4,1,6,2,9,3]這個數(shù)組舉例。
第一遍遍歷：
先進行拆分?[4,1,6,2,9,3] 選擇元素 4 作為軸心點
檢查是否?1 < 4 (軸心點)
檢查是否?6 < 4 (軸心點)
檢查是否?2 < 4 (軸心點)
2 < 4 (軸心點) 是為真，將指數(shù)2和 存儲指數(shù) 6 進行交換
檢查是否?9 < 4 (軸心點)
檢查是否?3 < 4 (軸心點)
3 < 4 (軸心點) 為真，將指數(shù)3和存儲指數(shù)6 進行交換
將軸心點4和存儲指數(shù)3進行交換
此時軸心點4左邊全部小于4，右邊大于4
目前數(shù)組順序為[3，1，2，4，9，6]。
下一步：
先將左邊先排好序
選擇元素 3 作為軸心點
檢查是否?1 < 3 (軸心點)
檢查是否 2 < 3 (軸心點)
將軸心點 3和存儲指數(shù)值 2進行交換
現(xiàn)在軸心點已經(jīng)在排序過后的位置
進行拆分?[2,1] 選擇 2 作為軸心點
檢查是否?1 < 2 (軸心點)
左邊遍歷完成，將軸心點2和存儲指數(shù)1 進行交換
右邊同理……避免視覺疲勞就不一一描述了，可看下面動態(tài)演示圖。
2. 快速排序法全流程
3. 快速排序法總結(jié)
默認(rèn)取第一個元素為軸心點（軸心點的確認(rèn)區(qū)分了 “快速排序法”和“隨機排序法”）兩種算法，而隨機排序則隨機rand一個元素為軸心點；
如果兩個不相鄰元素交換，可以一次交換消除多個逆序，加快排序進程。
二、計數(shù)排序法
計數(shù)排序，顧名思義，就是把要排序的元素都一一計數(shù)，某個數(shù)值如果總共有5個相同的，該元素對應(yīng)的個數(shù)就記為5；總共有10個相同的，就記為10。
1. 計數(shù)排序法基本思路
創(chuàng)建計數(shù)器；
遍歷數(shù)組中的每個元素在相應(yīng)的計數(shù)器增加1；
將計數(shù)器儲存好的元素從小到大重新收集；
重新將計數(shù)器元素重新存儲于原數(shù)組。
下面通過圖文形式一步一步進行案例拆解。
拿[8,6,4,1,6,2,9,6,2,4,3]這個數(shù)組舉例。
創(chuàng)建計數(shù)器1-9從小到大依次排列，然后遍歷數(shù)組里每一個元素對應(yīng)丟到相應(yīng)計數(shù)器
將8存到計數(shù)器8 此時計數(shù)器8有1個元素
將6存到計數(shù)器6 此時計數(shù)器6有1個元素
將4存到計數(shù)器4 此時計數(shù)器4有1個元素
將1存到計數(shù)器1 此時計數(shù)器1有1個元素
將6存到計數(shù)器6 此時計數(shù)器6有2個元素
將2存到計數(shù)器2 此時計數(shù)器2有1個元素
將9存到計數(shù)器9 此時計數(shù)器9有1個元素
將6存到計數(shù)器6 此時計數(shù)器6有3個元素
將2存到計數(shù)器2 …..
將4存到計數(shù)器4 ……
將3存到計數(shù)器3 ……
第二步：
將計數(shù)器里面的數(shù)組從小到大依次儲存于新數(shù)組列表
計數(shù)器1 有1個元素 重新放入新列表[1]
計數(shù)器2 有2個元素 重新放入新列表[1，2，2]
計數(shù)器3 有1個元素 重新放入新列表[1，2，2，3]
計數(shù)器4 有2個元素 重新放入新列表[1，2，2，3，4，4]
計數(shù)器6 有3個元素 重新放入新列表[1，2，2，3，4，4，6，6，6]
計數(shù)器8 有1個元素 重新放入新列表[1，2，2，3，4，4，6，6，6，8]
計數(shù)器9 有1個元素 重新放入新列表[1，2，2，3，4，4，6，6，6，8，9]
2. 計數(shù)排序全流程
3. 計數(shù)排序總結(jié)
排序不需要進行比較
在當(dāng)待排序數(shù)組內(nèi)有大量重復(fù)的數(shù)值并且這些數(shù)值較為集中時，使用計數(shù)排序有明顯的優(yōu)勢
除了以上兩種排序算法，還有許多不同的排序算法，每個都有其自身的優(yōu)點和使用場景，當(dāng)然也有局限性。可以多看幾遍全流程動態(tài)圖弄清來龍去脈，理解性地記憶，希望對你有用。
再附上之前一篇文章：走進開發(fā)，5分鐘熟悉3種經(jīng)典排序算法
微信公眾號：首席吹牛官，人人都是產(chǎn)品經(jīng)理專欄作家。互聯(lián)網(wǎng)圈十八線作詞人，國家一級退堂鼓表演藝術(shù)家。顏良而文丑，歡迎交流。
