前面講的都是基于比較交換的算法拂铡，那有沒有不使用比較就能排序的算法呢？它們的復(fù)雜度會(huì)不會(huì)更優(yōu)呢？
接下來在后面的系列文章中芯急，我將一一介紹O(n)線性的排序方法：
- 計(jì)數(shù)排序
- 桶排序
- 基數(shù)排序
這一篇文章我們就先來學(xué)習(xí)什么是計(jì)數(shù)排序：
計(jì)數(shù)排序
計(jì)數(shù)排序是針對(duì)給定范圍的隊(duì)列，創(chuàng)建這個(gè)范圍大小的數(shù)組驶俊，初始值都為0娶耍，然后遍歷隊(duì)列，將數(shù)字放至到對(duì)應(yīng)的下標(biāo)位置饼酿，如果出現(xiàn)1次榕酒，則計(jì)數(shù)+1胚膊，直至遍歷完成，就將所有的數(shù)字都放入這個(gè)數(shù)組里了想鹰。
然后再次遍歷這個(gè)數(shù)組紊婉，按照數(shù)組下標(biāo)，將取出對(duì)應(yīng)的值辑舷，如果計(jì)數(shù)為幾喻犁，就按順序出現(xiàn)幾次，將這些值放入一個(gè)新數(shù)組中何缓，遍歷完成后肢础，就可以得到有序隊(duì)列了
下面，按常碌廓，舉個(gè)栗子：
初始的無序數(shù)組传轰，假設(shè)總共有12個(gè)數(shù)，假設(shè)所有值都在0-10之間取氓皱，這12個(gè)值分別為：1路召、3、4波材、6股淡、8、9廷区、1唯灵、2、3隙轻、10埠帕、7、5
- 創(chuàng)建一個(gè)長(zhǎng)度為11的數(shù)組玖绿，初始值全設(shè)為0：[0,0,0,0,0,0,0,0,0,0,0]
- 遍歷這12個(gè)值敛瓷，第1個(gè)為1，將數(shù)組下標(biāo)為1的位置斑匪，計(jì)數(shù)加1 ：[0,1,0,0,0,0,0,0,0,0,0]
- 第2個(gè)為3呐籽，將數(shù)組下標(biāo)為3的位置，計(jì)數(shù)加1： [0,1,0,1,0,0,0,0,0,0,0,0]
... - 直到所有數(shù)字遍歷完成蚀瘸，結(jié)果為：[0,2,1,2,1,1,1,1,1,1,1]
- 這時(shí)候狡蝶，遍歷這個(gè)數(shù)組，取出對(duì)應(yīng)下標(biāo)的值贮勃，根據(jù)次數(shù)贪惹，放到一個(gè)新隊(duì)列中
- 比如，下標(biāo)為0的計(jì)數(shù)為0寂嘉，代表沒有數(shù)字奏瞬，忽略枫绅；
- 下標(biāo)為1的數(shù)字計(jì)數(shù)為2，代表1出現(xiàn)了2次丝格，則新隊(duì)列結(jié)果為:[1,1]
- 下標(biāo)為2的數(shù)字計(jì)數(shù)為1撑瞧，代表2出現(xiàn)了1次棵譬，則往新隊(duì)列中添加元素[1,1,2]
... - 最后显蝌，可以得到最終的結(jié)果[1,1,2,3,3,4,5,6,7,8,9,10]，這就是我們想要的有序隊(duì)列了
計(jì)數(shù)算法的優(yōu)化
如果這個(gè)序列的范圍不是從0開始订咸，而是從某個(gè)值到某個(gè)值之間曼尊，比如是500-600之間取值，這其實(shí)只用了101個(gè)空間脏嚷，這時(shí)候如果從創(chuàng)建從0-600的初始數(shù)組骆撇，這無疑浪費(fèi)了0-499的空間，計(jì)算機(jī)說不要占著茅坑不干事父叙！
所以要優(yōu)化一下神郊，只創(chuàng)建101個(gè)空間大小，來放置500-600間的數(shù)趾唱，那么這個(gè)關(guān)系怎么對(duì)應(yīng)上呢涌乳？
其實(shí)只要下標(biāo) + min就是我們對(duì)應(yīng)的值了，比如500放到下標(biāo)為0的位置甜癞，到時(shí)取出來的值時(shí)夕晓，就下標(biāo)0 + 500，就是我們想到的值了
/**
* @description 實(shí)現(xiàn)計(jì)數(shù)算法
* @param arr: 初始的無序隊(duì)列（一般為指定范圍）
* @return res: 計(jì)數(shù)排序后的有序隊(duì)列
*/
function countSort(arr) {
// 計(jì)算出原始數(shù)組的最大最小值
let max = arr[0]
let min = arr[0]
const len = arr.length
for(let i = 0; i< len; i++) {
if(arr[i] > max) {
max = arr[i]
}
if(arr[i] < min) {
min = arr[i]
}
}
// 計(jì)算計(jì)數(shù)數(shù)組的容量
const countLen = max - min + 1
let countArr = new Array(countLen).fill(0) // 創(chuàng)建計(jì)數(shù)數(shù)組悠咱，并設(shè)置所有數(shù)的計(jì)數(shù)初始值為0
// 遍歷初始數(shù)組蒸辆，給對(duì)應(yīng)下標(biāo)(arr[j] - min)計(jì)數(shù)加1
for(let j = 0; j < len; j++ ) {
countArr[arr[j] - min]++;
}
// 結(jié)果隊(duì)列
let res = []
// 遍歷結(jié)果隊(duì)列的指針
let resIndex = 0
for(let k = 0; k < countLen; k++) {
// 如果某數(shù)計(jì)數(shù)大于0，就循環(huán)取出值
while(countArr[k] > 0) {
// 將此數(shù)放入結(jié)果隊(duì)列中
res[resIndex] = k + min
// 隊(duì)列指針右移
resIndex++;
// 計(jì)數(shù)減1
countArr[k]--;
}
}
return res
}
// 使用console.time()和console.timeEnd()這一句語句析既，會(huì)輸出中間程序執(zhí)行的運(yùn)行時(shí)間
console.time()
const arr = [544,522,522,533,511,522,551,552,553,510,557,555]
let res = countSort(arr)
console.log('res:', res); // [ 510, 511, 522, 522, 522, 533, 544, 551, 552, 553, 555, 557 ]
console.timeEnd() // default: 4.135ms
計(jì)數(shù)算法的再次優(yōu)化
之前計(jì)算排序已經(jīng)實(shí)現(xiàn)排序的基本功能了躬贡？但是，我們會(huì)發(fā)現(xiàn)眼坏，它把相同的部分拂玻，使用計(jì)數(shù)方式存儲(chǔ)后，這幾個(gè)相同部分空骚，我就分不清它在初始隊(duì)列中哪個(gè)先哪個(gè)后出現(xiàn)的了纺讲，是一個(gè)不穩(wěn)定的算法
比如:[3,1,2,1]，當(dāng)計(jì)數(shù)統(tǒng)計(jì)后為：[2,1,1]囤屹，那么在1位置上的兩個(gè)1熬甚，最終會(huì)變成:[1,1,2,3]排序后我是分不清之前是哪個(gè)1先哪個(gè)1后，如果我希望排序后肋坚，不要改變相同元素的相對(duì)位置乡括，也就是讓它變成一個(gè)穩(wěn)定的算法肃廓，要怎么做呢？
要實(shí)現(xiàn)這個(gè)功能诲泌，其實(shí)就是把當(dāng)前元素的計(jì)數(shù)改成： 前面所有元素計(jì)數(shù)之和 + 當(dāng)前元素計(jì)數(shù)盲赊，這樣，對(duì)應(yīng)下標(biāo)元素對(duì)應(yīng)的那個(gè)元素的計(jì)數(shù)敷扫，就是它最終序列的位置哀蘑，有一些繞，還是來講栗子吧：
比如：
初始[3,1,2,1,5]
-
按照之前優(yōu)化1的算法：
最大值max為5葵第，最小值min為1绘迁，那么設(shè)置空間為3的計(jì)數(shù)數(shù)組[0,0,0,0,0]：- 下標(biāo)0對(duì)應(yīng)元素1 (下標(biāo)+min，就是它所對(duì)應(yīng)的元素值)卒密，下標(biāo)所在位置放置元素1的計(jì)數(shù)2, [2,0,0,0,0]
- 下標(biāo)1對(duì)應(yīng)元素2缀台，下標(biāo)所在位置放置元素2的計(jì)數(shù)1, [2,1,0,0,0]
- 下標(biāo)2對(duì)應(yīng)元素3，下標(biāo)所在位置放置元素3的計(jì)數(shù)1, [2,1,1,0,0]
- 下標(biāo)4對(duì)應(yīng)元素5哮奇，下標(biāo)所在位置放置元素5的計(jì)數(shù)1, [2,1,1,0,1]
這時(shí)膛腐，遍歷計(jì)數(shù)數(shù)組，根據(jù)下標(biāo)所在得出: - 下標(biāo)0鼎俘，對(duì)應(yīng)元素是1哲身，計(jì)數(shù)為2，所以生成新數(shù)組[1,1]
- 下標(biāo)1而芥，對(duì)應(yīng)元素2律罢，計(jì)數(shù)為1，所以生成新數(shù)組[1,1,2]
- 下標(biāo)2棍丐，對(duì)應(yīng)元素3误辑，計(jì)數(shù)為1，所以生成新數(shù)組[1,1,2,3]
- 下標(biāo)3歌逢，因?yàn)橛?jì)數(shù)為0巾钉，忽略
- 下標(biāo)5，對(duì)應(yīng)元素5秘案，計(jì)數(shù)為1砰苍，所以就生成新數(shù)組[1,1,2,3,5]
-
按照現(xiàn)在優(yōu)化2的算法：
最大值max為5，最小值min為1阱高，計(jì)數(shù)數(shù)組[0,0,0,0,0]：- 下標(biāo)0對(duì)應(yīng)元素1 (下標(biāo)+min赚导，就是它所對(duì)應(yīng)的元素值)，下標(biāo)所在位置放置元素1的計(jì)數(shù)2, [2,0,0]
- 下標(biāo)1對(duì)應(yīng)元素2赤惊，下標(biāo)所在位置放置元素2的自身計(jì)數(shù)1 + 前面元素的計(jì)數(shù)2 = 計(jì)數(shù)3, [2,3,0]
- 下標(biāo)2對(duì)應(yīng)元素3吼旧，下標(biāo)所在位置放置元素3的自身計(jì)數(shù)1 + 前面元素的計(jì)數(shù)3 = 計(jì)數(shù)4, 最終的計(jì)數(shù)數(shù)組為：[2,3,4]
- 下標(biāo)3對(duì)應(yīng)元素4，下標(biāo)所在位置放置元素3的自身計(jì)數(shù)0 + 前面元素的計(jì)數(shù)4 = 計(jì)數(shù)4, 最終的計(jì)數(shù)數(shù)組為：[2,3,4,4]
- 下標(biāo)4對(duì)應(yīng)元素5未舟，下標(biāo)所在位置放置元素5的自身計(jì)數(shù)1 + 前面元素的計(jì)數(shù)4 = 計(jì)數(shù)5, 最終的計(jì)數(shù)數(shù)組為：[2,3,4,4,5]
這時(shí)候圈暗，創(chuàng)建一個(gè)跟原數(shù)組一樣大小的空數(shù)組掂为，從后向前遍歷初始數(shù)組，根據(jù)元素獲取對(duì)應(yīng)計(jì)數(shù)數(shù)組中下標(biāo)（元素值-min）的計(jì)數(shù)值员串，就是它的最終位置勇哗，并更新其計(jì)數(shù)-1，代表下一次相同元素要放置的位置：
- 遍歷[3,1,2,1,5]最后一個(gè)數(shù)5,它的計(jì)數(shù)下標(biāo)位置為：5-min=5-1=4,查看計(jì)數(shù)數(shù)組下標(biāo)為4的值寸齐，為5欲诺，代表代表它放置在新數(shù)組的第5位[,,,,5]，此時(shí)访忿，計(jì)數(shù)數(shù)組更新5的計(jì)數(shù)為：5-1=4瞧栗，代表下一次相同元素應(yīng)該放置的位置[2,3,4,4,4]斯稳；
- 遍歷倒數(shù)第二個(gè)數(shù)1海铆，它的計(jì)數(shù)下標(biāo)位置：1-1=0，查看計(jì)數(shù)數(shù)組下標(biāo)為0的值挣惰，為計(jì)數(shù)2卧斟，代表它放置在新數(shù)據(jù)的第2數(shù)，[,1,,,5]憎茂，此時(shí)珍语，計(jì)數(shù)數(shù)組更新1的計(jì)數(shù)為：2-1=1，代表下一次相同元素應(yīng)該放置的位置竖幔，計(jì)數(shù)數(shù)組更新為：[1,3,4,4,4]板乙；
- 遍歷倒數(shù)三個(gè)數(shù)2，它的計(jì)數(shù)下標(biāo)位置: 2-1=1拳氢，查看計(jì)數(shù)數(shù)組下標(biāo)為1的值募逞，為計(jì)數(shù)3，代表它放置在新數(shù)據(jù)的第3位馋评，[,1,2,,5]放接，此時(shí)，計(jì)數(shù)數(shù)組更新2的計(jì)數(shù)為：3-1=2留特，代表下一次相同元素應(yīng)該放置的位置纠脾，計(jì)數(shù)數(shù)組更新為：[1,2,4,4,4]；
- 遍歷倒數(shù)第四個(gè)數(shù)1蜕青，它的計(jì)數(shù)下標(biāo)位置1-1=0苟蹈，計(jì)數(shù)數(shù)組下標(biāo)為1的值已經(jīng)在上一次更新為1，所以此時(shí)右核，把它放在新數(shù)組第1的位置[1,1,2,,5],計(jì)數(shù)數(shù)組更新為[0,2,4,4,4]
- 遍歷第一個(gè)數(shù)3慧脱，它的計(jì)數(shù)下標(biāo)位置為：3-min = 3-1 = 2，查看計(jì)數(shù)數(shù)組下標(biāo)為2的值蒙兰，為4磷瘤，代表它放置在新數(shù)組的第4位[1,1,2,3,5]芒篷，計(jì)數(shù)數(shù)組更新為[0,2,3,4,4]，至此采缚，排序結(jié)束
這時(shí)候發(fā)現(xiàn)针炉，越往后的出現(xiàn)相同元素的位置越后，這樣就實(shí)現(xiàn)穩(wěn)定的計(jì)數(shù)排序了
/**
* @description 優(yōu)化版：實(shí)現(xiàn)穩(wěn)定的計(jì)數(shù)排序
* @param arr: 初始的無序隊(duì)列（一般為指定范圍）
* @return res: 計(jì)數(shù)排序后的有序隊(duì)列
*/
function stableCountSort(arr) {
let max = arr[0]
let min = arr[0]
const len = arr.length
for(let i = 0; i< len; i++) {
if(arr[i] > max) {
max = arr[i]
}
if(arr[i] < min) {
min = arr[i]
}
}
const countLen = max - min + 1
// 前面創(chuàng)建計(jì)數(shù)數(shù)組的步驟不變
let countArr = new Array(countLen).fill(0)
for(let j = 0; j < len; j++ ) {
countArr[arr[j] - min]++;
}
// 就增加了：從第2個(gè)數(shù)開始扳抽，將后面元素的計(jì)數(shù)變成與前面所有元素的計(jì)數(shù)之和
for(let z = 1; z < countLen; z++) {
// 加上前一位的計(jì)數(shù)次數(shù)（也就是之前所有元素的計(jì)數(shù)之和）
countArr[z] += countArr[z -1]
}
console.log('2222', countArr); // 此時(shí)篡帕，計(jì)數(shù)數(shù)組：[ 2, 3, 4, 4, 5 ]
// 結(jié)果隊(duì)列
let res = new Array(len)
let countIndex = 0
// 對(duì)初始序列，進(jìn)行從后往前遍歷
for(let k = len - 1; k >= 0; k--) {
// 獲取元素對(duì)應(yīng)的計(jì)數(shù)
countIndex = countArr[arr[k] - min]
// 因?yàn)橄聵?biāo)0占了一位贸呢，所以下標(biāo)要減1
res[countIndex - 1] = arr[k]
console.log(res)
countArr[arr[k] - min]--;
}
return res
}
const arr1 = [3,1,2,1,5]
res = stableCountSort(arr1)
console.log('res2:', res); // [ 1, 1, 2, 3, 5 ]
計(jì)數(shù)排序的局限性
雖然計(jì)數(shù)排序的時(shí)間復(fù)雜度只有O(n)镰烧，為什么我們很少用到它呢？因?yàn)樗斜容^大的局限性：
- 當(dāng)數(shù)列最大和最小值的差距過大時(shí)楞陷，并不適合怔鳖；過大的差距意思空間上的消耗也要隨之變 大。不但浪費(fèi)空間固蛾，而且時(shí)間復(fù)雜度也會(huì)隨之升高
- 當(dāng)數(shù)列元素不是整數(shù)時(shí)结执，也不適合。比如小數(shù)艾凯，就無法根據(jù)元素創(chuàng)建對(duì)應(yīng)的計(jì)數(shù)數(shù)組献幔。
總結(jié)
- 時(shí)間復(fù)雜度：
- 獲取最大最小值O(n)
- 獲取計(jì)數(shù)數(shù)組O(n)
- 獲取累加計(jì)數(shù)數(shù)組O(n)
- 遍歷初始數(shù)組O(n)
總的是O(4n)，還是約等于O(n)
- 空間復(fù)雜度
- 創(chuàng)建計(jì)數(shù)數(shù)組空間O(n)
- 結(jié)果隊(duì)列O(n)
總的是O(2n)趾诗，還是約等于O(n)
- 是一種典型的空間換時(shí)間的算法
- 優(yōu)化后的計(jì)數(shù)排序已經(jīng)是穩(wěn)定的排序方法
排序算法系列文章傳送門(未完蜡感，持續(xù)更新中)：
排序算法-1（javascript） 冒泡、選擇恃泪、插入郑兴、希爾排序的實(shí)現(xiàn)
排序算法-2（javascript） 快速排序的實(shí)現(xiàn)
排序算法-3（javascript） 堆排序的實(shí)現(xiàn)
排序算法-4（javascript） 歸并排序的實(shí)現(xiàn)
排序算法-5（javascript） 計(jì)數(shù)排序的實(shí)現(xiàn)
