若干年前pony在騰訊產(chǎn)品暨技術(shù)峰會(huì)上就說(shuō)過(guò)：“我們希望的產(chǎn)品經(jīng)理是從技術(shù)晉升而來(lái)的?！奔夹g(shù)是實(shí)施手段，產(chǎn)品最終還是要靠技術(shù)來(lái)實(shí)現(xiàn)，產(chǎn)品還是不能遠(yuǎn)離技術(shù)。

那么不想通過(guò)枯燥的代碼來(lái)理解幾大排序算法，本文通過(guò)動(dòng)態(tài)可視化圖來(lái)解析冒泡排序、選擇排序及插入排序。

排序算法最終目的是讓無(wú)序的數(shù)據(jù)組合變成有序的數(shù)據(jù)組合。

一、冒泡法

從字面上能理解， “冒泡”即小值的浮上來(lái)，大值沉下去。

1. 冒泡排序法基本思路

第一步比較相鄰的元素大小。如果第一個(gè)比第二個(gè)大，就交換兩個(gè)元素位置。

之后對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)最后的元素應(yīng)該會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

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

拿[20，10，15，30，12]這個(gè)數(shù)組舉例。

第一遍循環(huán)

檢查是否 20 > 10；是，交換元素位置；

檢查是否 20 > 15；是，交換元素位置；

檢查是否 20 > 30；否，位置不做交換；

檢查是否 30 > 12；是，交換元素位置；

第一遍循環(huán)結(jié)束，此時(shí)將最后一個(gè)沒(méi)有排序過(guò)的元素標(biāo)記為已排序（即30）。因?yàn)樵谧罱囊淮螔呙柽^(guò)程中至少有一次交換發(fā)生過(guò)，我們可以進(jìn)行另一輪掃描。此輪掃描只需要循環(huán)判斷前面4個(gè)元素。

第二遍循環(huán)開(kāi)始

檢查是否 10 大于 15；否，位置不做交換；

檢查是否 15 大于 20；否，位置不做交換；

檢查是否 20 大于 12； 是，交換元素位置；

此時(shí)標(biāo)記 “20”為已排序，那么同理下一輪循環(huán)遍歷只需循環(huán)判斷前面3個(gè)元素。

……….

避免視覺(jué)疲勞，圖文只說(shuō)明前面2輪循環(huán)，下面的3輪循環(huán)大家自己思考和理解。

2. 冒泡排序法全流程

3. 冒泡法總結(jié)

每一輪左右元素兩兩比較，不進(jìn)行跨元素比較

每一輪循環(huán)比較都會(huì)產(chǎn)生當(dāng)前最大值（當(dāng)前最大值：這一輪下來(lái)的最大值）

每一輪循環(huán)后就會(huì)少一個(gè)元素進(jìn)行比較（因?yàn)槊拷Y(jié)束一輪就會(huì)產(chǎn)生一個(gè)當(dāng)前最大值）

二、選擇排序法

選擇排序是從冒泡排序演化而來(lái)，每一輪比較得出最小的那個(gè)值，然后依次和每輪“無(wú)序區(qū)”中參與比較的第一個(gè)值進(jìn)行交換。

1. 選擇排序法基本思路

初始時(shí)在序列中找到最小元素

放到序列的起始位置作為已排序序列

然后再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，放到已排序序列的末尾

以此類推，直到所有元素均排序完畢

注意選擇排序與冒泡排序的區(qū)別：

冒泡排序通過(guò)依次交換相鄰兩個(gè)順序不合法的元素位置，從而將當(dāng)前最大元素放到合適的位置；而選擇排序每循環(huán)遍歷一次都記住了當(dāng)前最小元素的位置，最后僅需一次交換操作即可將其放到合適的位置。

下面還是以[20，10，15，30，12]這個(gè)數(shù)組舉例。

第一遍循環(huán)

先把最小值設(shè)置成為 20 , 然后通過(guò)遍歷剩下的沒(méi)有排序過(guò)的元素來(lái)找到真正的最小值；

檢查是否 10 小于現(xiàn)在的最小值 (20)。是，將 10 設(shè)為新的最小值；

檢查是否 15 小于現(xiàn)在的最小值 (10)。否，10仍然是最小值；

檢查是否 30 小于現(xiàn)在的最小值 (10)。否，10仍然是最小值；

檢查是否 12 小于現(xiàn)在的最小值 (10)。否，10仍然是最小值。

一輪過(guò)后，最小值出現(xiàn)。

交換最小的元素 (10) 和第一個(gè)沒(méi)有排序過(guò)的元素 (20)。

現(xiàn)在10是被認(rèn)定整個(gè)數(shù)組最小的值。

第二遍循環(huán)

把現(xiàn)在的最小值設(shè)置成為 20 , 然后通過(guò)遍歷剩下的沒(méi)有排序過(guò)的元素來(lái)找到真正的最小值；

檢查是否 15 小于現(xiàn)在的最小值 (20)。是，將 15 設(shè)為新的最小值；

檢查是否 30 小于現(xiàn)在的最小值 (15)。否，15仍然是最小值；

檢查是否 12小于現(xiàn)在的最小值 (15)。是，將 12 設(shè)為新的最小值；

交換最小的元素 (12) 和第一個(gè)沒(méi)有排序過(guò)的元素 (20)；

數(shù)組排序順序更新為 10 12 15 30 20。

避免視覺(jué)疲勞，圖文只說(shuō)明前面2輪循環(huán)，下面的3輪循環(huán)大家自己思考和理解。

2. 選擇排序法全流程

3. 選擇排序法總結(jié)

每一輪進(jìn)行跨元素比較

每一輪循環(huán)比較都會(huì)產(chǎn)生當(dāng)前最小值（當(dāng)前最小值：這一輪下來(lái)的最小值）

每一輪循環(huán)比較后就會(huì)少一個(gè)元素進(jìn)行比較（因?yàn)槊拷Y(jié)束一輪就會(huì)產(chǎn)生一個(gè)當(dāng)前最小值）

三、插入排序法（直接插入）

插入排序是基于互相比較的排序。所謂的“比較”，就是通過(guò)比較數(shù)組中的元素，看誰(shuí)大誰(shuí)小，根據(jù)結(jié)果對(duì)應(yīng)調(diào)整元素的位置。

1. 插入排序法基本思路

初始時(shí)先默認(rèn)將第一個(gè)元素標(biāo)記為已排序

然后提取第一個(gè)沒(méi)有排序過(guò)的元素，找出插入提取元素的地方并和已經(jīng)排序過(guò)的元素進(jìn)行比較。

比較大小若條件成立，則將已排序過(guò)的元素往右移1個(gè)單位，如果條件不成立，則在現(xiàn)有位置直接插入。

以此類推，直到所有元素均排序完畢

還以[20，10，15，30，12]這個(gè)數(shù)組舉例

將第一個(gè)元素 (20) 標(biāo)記為已經(jīng)排序過(guò)；

提取第一個(gè)沒(méi)有排序過(guò)的元素 (10)；

找出插入提取元素的地方；和已經(jīng)排序過(guò)的元素 20 比較；

20 大于 10 成立,  則將現(xiàn)在已經(jīng)排序過(guò)的元素20向右移動(dòng)1格；

在數(shù)組的最開(kāi)始（沒(méi)有東西可以比較），則在現(xiàn)有位置上插入元素。

提取第一個(gè)沒(méi)有排序過(guò)的元素 (15)；

找出插入提取元素的地方；和已經(jīng)排序過(guò)的元素 20 比較；

20 大于 15 成立,  則將現(xiàn)在已經(jīng)排序過(guò)的元素20 向右移動(dòng)1格；

10 大于 15 不成立, 在現(xiàn)有位置上插入一個(gè)元素；

提取第一個(gè)沒(méi)有排序過(guò)的元素 (30)；

找出插入提取元素的地方；和已經(jīng)排序過(guò)的元素 20 比較。

20 大于 30 不成立, 在現(xiàn)有位置上插入一個(gè)元素；

提取第一個(gè)沒(méi)有排序過(guò)的元素 (12)。

……..

避免篇幅過(guò)大導(dǎo)致視覺(jué)疲勞，下面幾步大家進(jìn)行自我思考和理解。

2. 插入排序法全流程

3. 插入排序法總結(jié)

由“有序組”和“待插入組”組成

每一輪都有一個(gè)待插入對(duì)象（可以接收實(shí)時(shí)數(shù)據(jù)進(jìn)行排序）直到“待插入組元素為0”

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