若干年前pony在騰訊產(chǎn)品暨技術(shù)峰會(huì)上就說過：“我們希望的產(chǎn)品經(jīng)理是從技術(shù)晉升而來的。”技術(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è)元素位置。
- 之后對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(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é)果對應(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è)待插入對象（可以接收實(shí)時(shí)數(shù)據(jù)進(jìn)行排序）直到“待插入組元素為0”
除了以上三種排序算法，還有許多不同的排序算法，每個(gè)都有其自身的優(yōu)點(diǎn)和使用場景，當(dāng)然也有局限性?？梢远嗫磶妆槿鞒虅?dòng)態(tài)圖弄清來龍去脈，理解性地記憶，希望對你有用。
本文由 @動(dòng)物園園長 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載
題圖來自 Pexels ，基于 CC0 協(xié)議
愛盈利-運(yùn)營小咖秀(www.jza6.com) 始終堅(jiān)持研究分享移動(dòng)互聯(lián)網(wǎng)App運(yùn)營推廣經(jīng)驗(yàn)、策略、全案、渠道等純干貨知識內(nèi)容；是廣大App運(yùn)營從業(yè)者的知識啟蒙、成長指導(dǎo)、進(jìn)階學(xué)習(xí)的集聚平臺；
想了解更多移動(dòng)互聯(lián)網(wǎng)干貨知識，請關(guān)注微信公眾號運(yùn)營小咖秀（ID: yunyingshow）
