本文通過動(dòng)態(tài)可視化圖來解析快速排序法和計(jì)數(shù)排序法。

這幾天“手機(jī)殼顏色換主題色”需求引起一波轟動(dòng)，關(guān)于事情真?zhèn)芜@里不做判斷。但技術(shù)仍然是實(shí)施手段，產(chǎn)品最終還是要靠技術(shù)來實(shí)現(xiàn)，產(chǎn)品還是不能遠(yuǎn)離技術(shù)。多理解一點(diǎn)技術(shù)知識(shí)，和開發(fā)大佬說話就多了一份硬氣。連基礎(chǔ)的排序算法都不懂的產(chǎn)品經(jīng)理很難的得到開發(fā)及項(xiàng)目組的青睞。

那么你花5分鐘閱讀，再花5分鐘理解。以后就可以在公司走路帶風(fēng)，抬頭挺胸。

關(guān)于“冒泡排序、插入及選擇排序”可以看之前一篇文章：走進(jìn)開發(fā)，5分鐘熟悉3種經(jīng)典排序算法

一、快速排序法

快速排序是冒泡排序的改進(jìn)版，整個(gè)過程就在拆拆補(bǔ)補(bǔ)，東拆西補(bǔ)或西拆東補(bǔ)，一邊拆一邊補(bǔ)，直到所有元素達(dá)到有序狀態(tài)。

1. 快速排序法基本思路

先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)，然后進(jìn)行大小分區(qū)；

分區(qū)過程，將比這個(gè)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊；

再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)，排序完成。

下面先通過圖文形式一步一步進(jìn)行拆解。

拿[4,1,6,2,9,3]這個(gè)數(shù)組舉例。

第一遍遍歷：

先進(jìn)行拆分?[4,1,6,2,9,3] 選擇元素 4 作為軸心點(diǎn)

檢查是否?1 < 4 (軸心點(diǎn))

檢查是否?6 < 4 (軸心點(diǎn))

檢查是否?2 < 4 (軸心點(diǎn))

2 < 4 (軸心點(diǎn)) 是為真，將指數(shù)2和 存儲(chǔ)指數(shù) 6 進(jìn)行交換

檢查是否?9 < 4 (軸心點(diǎn))

檢查是否?3 < 4 (軸心點(diǎn))

3 < 4 (軸心點(diǎn)) 為真，將指數(shù)3和存儲(chǔ)指數(shù)6 進(jìn)行交換

將軸心點(diǎn)4和存儲(chǔ)指數(shù)3進(jìn)行交換

此時(shí)軸心點(diǎn)4左邊全部小于4，右邊大于4

目前數(shù)組順序?yàn)閇3，1，2，4，9，6]。

下一步：

先將左邊先排好序

選擇元素 3 作為軸心點(diǎn)

檢查是否?1 < 3 (軸心點(diǎn))

檢查是否 2 < 3 (軸心點(diǎn))

將軸心點(diǎn) 3和存儲(chǔ)指數(shù)值 2進(jìn)行交換

現(xiàn)在軸心點(diǎn)已經(jīng)在排序過后的位置

進(jìn)行拆分?[2,1] 選擇 2 作為軸心點(diǎn)

檢查是否?1 < 2 (軸心點(diǎn))

左邊遍歷完成，將軸心點(diǎn)2和存儲(chǔ)指數(shù)1 進(jìn)行交換

右邊同理……避免視覺疲勞就不一一描述了，可看下面動(dòng)態(tài)演示圖。

2. 快速排序法全流程

3. 快速排序法總結(jié)

默認(rèn)取第一個(gè)元素為軸心點(diǎn)（軸心點(diǎn)的確認(rèn)區(qū)分了 “快速排序法”和“隨機(jī)排序法”）兩種算法，而隨機(jī)排序則隨機(jī)rand一個(gè)元素為軸心點(diǎn)；

如果兩個(gè)不相鄰元素交換，可以一次交換消除多個(gè)逆序，加快排序進(jìn)程。

二、計(jì)數(shù)排序法

計(jì)數(shù)排序，顧名思義，就是把要排序的元素都一一計(jì)數(shù)，某個(gè)數(shù)值如果總共有5個(gè)相同的，該元素對(duì)應(yīng)的個(gè)數(shù)就記為5；總共有10個(gè)相同的，就記為10。

1. 計(jì)數(shù)排序法基本思路

創(chuàng)建計(jì)數(shù)器；

遍歷數(shù)組中的每個(gè)元素在相應(yīng)的計(jì)數(shù)器增加1；

將計(jì)數(shù)器儲(chǔ)存好的元素從小到大重新收集；

重新將計(jì)數(shù)器元素重新存儲(chǔ)于原數(shù)組。

下面通過圖文形式一步一步進(jìn)行案例拆解。

拿[8,6,4,1,6,2,9,6,2,4,3]這個(gè)數(shù)組舉例。

創(chuàng)建計(jì)數(shù)器1-9從小到大依次排列，然后遍歷數(shù)組里每一個(gè)元素對(duì)應(yīng)丟到相應(yīng)計(jì)數(shù)器

將8存到計(jì)數(shù)器8 此時(shí)計(jì)數(shù)器8有1個(gè)元素

將6存到計(jì)數(shù)器6 此時(shí)計(jì)數(shù)器6有1個(gè)元素

將4存到計(jì)數(shù)器4 此時(shí)計(jì)數(shù)器4有1個(gè)元素

將1存到計(jì)數(shù)器1 此時(shí)計(jì)數(shù)器1有1個(gè)元素

將6存到計(jì)數(shù)器6 此時(shí)計(jì)數(shù)器6有2個(gè)元素

將2存到計(jì)數(shù)器2 此時(shí)計(jì)數(shù)器2有1個(gè)元素

將9存到計(jì)數(shù)器9 此時(shí)計(jì)數(shù)器9有1個(gè)元素

將6存到計(jì)數(shù)器6 此時(shí)計(jì)數(shù)器6有3個(gè)元素

將2存到計(jì)數(shù)器2 …..

將4存到計(jì)數(shù)器4 ……

將3存到計(jì)數(shù)器3 ……

第二步：

將計(jì)數(shù)器里面的數(shù)組從小到大依次儲(chǔ)存于新數(shù)組列表

計(jì)數(shù)器1 有1個(gè)元素 重新放入新列表[1]

計(jì)數(shù)器2 有2個(gè)元素 重新放入新列表[1，2，2]

計(jì)數(shù)器3 有1個(gè)元素 重新放入新列表[1，2，2，3]

計(jì)數(shù)器4 有2個(gè)元素 重新放入新列表[1，2，2，3，4，4]

計(jì)數(shù)器6 有3個(gè)元素 重新放入新列表[1，2，2，3，4，4，6，6，6]

計(jì)數(shù)器8 有1個(gè)元素 重新放入新列表[1，2，2，3，4，4，6，6，6，8]

計(jì)數(shù)器9 有1個(gè)元素 重新放入新列表[1，2，2，3，4，4，6，6，6，8，9]

2. 計(jì)數(shù)排序全流程

3. 計(jì)數(shù)排序總結(jié)

排序不需要進(jìn)行比較

在當(dāng)待排序數(shù)組內(nèi)有大量重復(fù)的數(shù)值并且這些數(shù)值較為集中時(shí)，使用計(jì)數(shù)排序有明顯的優(yōu)勢(shì)

除了以上兩種排序算法，還有許多不同的排序算法，每個(gè)都有其自身的優(yōu)點(diǎn)和使用場(chǎng)景，當(dāng)然也有局限性?？梢远嗫磶妆槿鞒虅?dòng)態(tài)圖弄清來龍去脈，理解性地記憶，希望對(duì)你有用。

再附上之前一篇文章：走進(jìn)開發(fā)，5分鐘熟悉3種經(jīng)典排序算法

微信公眾號(hào)：首席吹牛官，人人都是產(chǎn)品經(jīng)理專欄作家?；ヂ?lián)網(wǎng)圈十八線作詞人，國(guó)家一級(jí)退堂鼓表演藝術(shù)家。顏良而文丑，歡迎交流。