《漫畫(huà)算法: 小灰的算法之旅》第4章 排序算法
引言
時(shí)間復(fù)雜度為O(n^2)的排序算法
冒牌排序、選擇排序、插入排序、希爾排序(它的性能略優(yōu)于O(n^2)，但又比不上O(nlogn))
時(shí)間復(fù)雜度為O(nlogn)的排序算法
快速排序、歸并排序、堆排序
時(shí)間復(fù)雜度為線性的排序算法
計(jì)數(shù)排序、桶排序、基數(shù)排序
排序算法還可以根據(jù)其穩(wěn)定性，劃分為穩(wěn)定排序和不穩(wěn)定排序
如果值相同的元素在排序后仍然保持著排序前的順序，則這樣的排序算法是穩(wěn)定排序；
如果值相同的元素在排序后打亂了排序前的順序，則這樣的排序算法是不穩(wěn)定排序
什么是冒泡排序
冒泡排序(bubble sort)：是一種基礎(chǔ)的交換排序
“漂”到了最右側(cè)
冒泡排序的第1輪就結(jié)束了，以此類(lèi)推，進(jìn)行多輪冒泡
冒泡排序是一種穩(wěn)定排序，值相等的元素并不會(huì)打亂原本的順序。由于該排序算法的每一輪都要遍歷所有元素，總共遍歷（元素?cái)?shù)量-1）輪，所以平均時(shí)間復(fù)雜度是O(n^2)
雞尾酒排序
雞尾酒排序的元素比較和交換過(guò)程是雙向的。
舉例：
[2, 3, 4, 5, 6, 7, 8, 1] 使用雞尾酒排序法
在雞尾酒排序的第3輪，需要重新從左向右比較并進(jìn)行交換；
1和2比較，位置不變；
2和3比較，位置不變；
3和4比較，位置不變……
6和7比較，位置不變。
沒(méi)有元素位置進(jìn)行交換，證明已經(jīng)有序，排序結(jié)束。
雞尾酒排序的思路：排序過(guò)程就像鐘擺一樣，第1輪從左到右，第2輪從右到左，第3輪再?gòu)淖蟮接摇?/p>
雞尾酒排序的優(yōu)點(diǎn)是能夠在特定條件下，減少排序的回合數(shù)；
而缺點(diǎn)也很明顯，就是代碼量幾乎增加了1倍；
它能發(fā)揮出優(yōu)勢(shì)的場(chǎng)景，是大部分元素已經(jīng)有序的情況
什么是快速排序
快速排序也屬于交換排序，通過(guò)元素之間的比較和交換位置來(lái)達(dá)到排序的目的；
冒泡排序在每一輪中只把1個(gè)元素冒泡到數(shù)列的一端，而快速排序則在每一輪挑選一個(gè)基準(zhǔn)元素，并讓其他比它大的元素移動(dòng)到數(shù)列一邊，比它小的元素移動(dòng)到數(shù)列的另一邊，從而把數(shù)列拆解成兩個(gè)部分
快速排序算法總體的平均時(shí)間復(fù)雜度是O(nlogn)
基準(zhǔn)元素(pivot)，在分治過(guò)程中，以基準(zhǔn)元素為中心，把其他元素移動(dòng)到它的左右兩邊
可以隨機(jī)選擇一個(gè)元素作為基準(zhǔn)元素，并且讓基準(zhǔn)元素和數(shù)列首元素交換位置
快速排序的平均時(shí)間復(fù)雜度是O(nlogn)，最壞情況下的時(shí)間復(fù)雜度是O(n^2)
快速排序的實(shí)現(xiàn)方法：
雙邊循環(huán)法
2.單邊循環(huán)法
從基準(zhǔn)元素的下一個(gè)位置開(kāi)始遍歷數(shù)組；
如果遍歷到的元素大于基準(zhǔn)元素，就繼續(xù)往后遍歷；
如果遍歷到的元素小于基準(zhǔn)元素，則需要做兩件事：
第一，把mark指針右移1位，因?yàn)樾∮趐ivot的區(qū)域邊界增大了1；
第二，讓最新遍歷到的元素和mark指針?biāo)谖恢玫脑亟粨Q位置，因?yàn)樽钚卤闅v的元素歸屬于小于pivot的區(qū)域
堆排序
堆排序算法：
把無(wú)序數(shù)組構(gòu)建成二叉堆。需要從小到大排序，則構(gòu)建成最大堆；需要從大到小排序，則構(gòu)建成最小堆。
循環(huán)刪除堆頂元素，替換到二叉堆的末尾，調(diào)整堆產(chǎn)生新的堆頂。
堆排序的時(shí)間復(fù)雜度為O(nlogn)
堆排序和快速排序的平均時(shí)間復(fù)雜度都是O(nlogn)，并且都是不穩(wěn)定排序；
至于不同點(diǎn)，快速排序的最壞時(shí)間復(fù)雜度是O(n^2)，而堆排序的最壞時(shí)間復(fù)雜度穩(wěn)定在O(nlogn)；
快速排序遞歸和非遞歸方法的平均空間復(fù)雜度都是O(logn)，而堆排序的空間復(fù)雜度是O(1)
計(jì)數(shù)排序和桶排序
[9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9，7，9]? 20個(gè)隨機(jī)整數(shù)
依此類(lèi)推
優(yōu)化版本的計(jì)數(shù)排序?qū)儆诜€(wěn)定排序
計(jì)數(shù)排序的時(shí)間復(fù)雜度
O(n+m)、空間復(fù)雜度為O(m)
計(jì)數(shù)排序的局限性：
當(dāng)數(shù)列最大和最小值差距過(guò)大時(shí)，并不適合用計(jì)數(shù)排序
當(dāng)數(shù)列元素不是整數(shù)時(shí)，也不適合用計(jì)數(shù)排序
桶排序
桶排序同樣是一種線性時(shí)間的排序算法
每一個(gè)桶(bucket)代表一個(gè)區(qū)間范圍
非整數(shù)列表: [4.5，0.84，3.25，2.18，0.5]
桶排序的總體時(shí)間復(fù)雜度為O(n);
至于空間復(fù)雜度就很容易得到了，同樣是O(n)
小結(jié)
