若干年前pony在騰訊產(chǎn)品暨技術(shù)峰會(huì)上就說過：“我們希望的產(chǎn)品經(jīng)理是從技術(shù)晉升而來的?！奔夹g(shù)是實(shí)施手段，產(chǎn)品最終還是要靠技術(shù)來實(shí)現(xiàn)，產(chǎn)品還是不能遠(yuǎn)離技術(shù)。那么不想通過枯燥的代碼來理解幾大排序算法，本文通過動(dòng)態(tài)可視化圖來解析冒泡排序、選擇排序及插入排序。

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

一、冒泡法

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

1. 冒泡排序法基本思路

• 第一步比較相鄰的元素大小。如果第一個(gè)比第二個(gè)大，就交換兩個(gè)元素位置。
• 之后對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
• 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
• 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

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

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

第一遍循環(huán)

• 檢查是否 20 > 10；是，交換元素位置；
• 檢查是否 20 > 15；是，交換元素位置；
• 檢查是否 20 > 30；否，位置不做交換；
• 檢查是否 30 > 12；是，交換元素位置；

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

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

• 檢查是否 10 大于 15；否，位置不做交換；
• 檢查是否 15 大于 20；否，位置不做交換；
• 檢查是否 20 大于 12；?是，交換元素位置；

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

……….

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

2. 冒泡排序法全流程

3. 冒泡法總結(jié)

• 每一輪左右元素兩兩比較，不進(jìn)行跨元素比較
• 每一輪循環(huán)比較都會(huì)產(chǎn)生當(dāng)前最大值（當(dāng)前最大值：這一輪下來的最大值）
• 每一輪循環(huán)后就會(huì)少一個(gè)元素進(jìn)行比較（因?yàn)槊拷Y(jié)束一輪就會(huì)產(chǎn)生一個(gè)當(dāng)前最大值）

二、選擇排序法

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

1. 選擇排序法基本思路

• 初始時(shí)在序列中找到最小元素
• 放到序列的起始位置作為已排序序列
• 然后再從剩余未排序元素中繼續(xù)尋找最小元素，放到已排序序列的末尾
• 以此類推，直到所有元素均排序完畢

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

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

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

第一遍循環(huán)

• 先把最小值設(shè)置成為?20 , 然后通過遍歷剩下的沒有排序過的元素來找到真正的最小值；
• 檢查是否?10 小于現(xiàn)在的最小值?(20)。是，將 10 設(shè)為新的最小值；
• 檢查是否?15 小于現(xiàn)在的最小值?(10)。否，10仍然是最小值；
• 檢查是否?30 小于現(xiàn)在的最小值?(10)。否，10仍然是最小值；
• 檢查是否?12 小于現(xiàn)在的最小值?(10)。否，10仍然是最小值。

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

交換最小的元素?(10) 和第一個(gè)沒有排序過的元素?(20)。

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

第二遍循環(huán)

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

• 檢查是否?15 小于現(xiàn)在的最小值?(20)。是，將 15 設(shè)為新的最小值；
• 檢查是否?30 小于現(xiàn)在的最小值?(15)。否，15仍然是最小值；
• 檢查是否?12小于現(xiàn)在的最小值?(15)。是，將 12 設(shè)為新的最小值；
• 交換最小的元素?(12) 和第一個(gè)沒有排序過的元素?(20)；

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

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

2. 選擇排序法全流程

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

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

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

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

1. 插入排序法基本思路

• 初始時(shí)先默認(rèn)將第一個(gè)元素標(biāo)記為已排序
• 然后提取第一個(gè)沒有排序過的元素，找出插入提取元素的地方并和已經(jīng)排序過的元素進(jìn)行比較。
• 比較大小若條件成立，則將已排序過的元素往右移1個(gè)單位，如果條件不成立，則在現(xiàn)有位置直接插入。
• 以此類推，直到所有元素均排序完畢

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

• 將第一個(gè)元素?(20) 標(biāo)記為已經(jīng)排序過；
• 提取第一個(gè)沒有排序過的元素?(10)；
• 找出插入提取元素的地方；和已經(jīng)排序過的元素 20 比較；
• 20 大于 10 成立, ?則將現(xiàn)在已經(jīng)排序過的元素20向右移動(dòng)1格；
• 在數(shù)組的最開始（沒有東西可以比較），則在現(xiàn)有位置上插入元素。

• 提取第一個(gè)沒有排序過的元素?(15)；
• 找出插入提取元素的地方；和已經(jīng)排序過的元素 20 比較；
• 20 大于 15 成立, ?則將現(xiàn)在已經(jīng)排序過的元素20 向右移動(dòng)1格；
• 10 大于 15 不成立, 在現(xiàn)有位置上插入一個(gè)元素；
• 提取第一個(gè)沒有排序過的元素?(30)；
• 找出插入提取元素的地方；和已經(jīng)排序過的元素 20 比較。
• 20 大于 30 不成立, 在現(xiàn)有位置上插入一個(gè)元素；
• 提取第一個(gè)沒有排序過的元素?(12)。
• ……..

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

2. 插入排序法全流程

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

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

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

本文由 @動(dòng)物園園長 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來自 Pexels ，基于 CC0 協(xié)議