小撒是一只好學(xué)的小鴨子，這天，小撒在學(xué)習(xí)算法
比較排序與線性時(shí)間排序
此前我們介紹的排序方法都是基于比較的蚓曼，而基于比較的排序方法存在Ω(n * log(n))的理論下界。
接下來(lái)我們要介紹的炸宵，是一系列能在線性時(shí)間內(nèi)完成排序的算法辟躏。
不過(guò)需要注意的是，相較于基于比較的算法土全，這些線性時(shí)間排序算法捎琐，并不具有普適性。
計(jì)數(shù)排序（Counting Sort）
計(jì)數(shù)排序便是一種線性時(shí)間排序算法裹匙。這里我們需要先假設(shè)：參與排序的所有元素瑞凑，都是介于 0 至 某個(gè)有限整數(shù) k 之間的整數(shù)。
我們首先創(chuàng)建一個(gè)長(zhǎng)度為k+1的計(jì)數(shù)數(shù)組概页，k為數(shù)組中的最大元素籽御。計(jì)數(shù)數(shù)組中的每一位用來(lái)對(duì)原數(shù)組中相應(yīng)元素出現(xiàn)的個(gè)數(shù)計(jì)數(shù)：
假設(shè)原數(shù)組是[2,3,1,2,0,3]，其中最大元素值為3惰匙，因此計(jì)數(shù)數(shù)組共有3 + 1 = 4個(gè)槽技掏，分別記錄原數(shù)組中0~3的元素個(gè)數(shù)，例如這里的[1,1,2,2]代表原數(shù)組有1個(gè)0项鬼，1個(gè)1哑梳，2個(gè)2以及2個(gè)3。
在此時(shí)绘盟，如果我們從頭遍歷計(jì)數(shù)數(shù)組鸠真，依次輸出按照個(gè)數(shù)輸出元素，即1個(gè)0龄毡，1個(gè)1吠卷，2個(gè)2以及2個(gè)3，那么我們就能得到排序后的結(jié)果：[1,1,2,2,3,3]沦零。
不過(guò)呢祭隔，我們想要的不僅如此，接下來(lái)路操，我們需要進(jìn)一步處理疾渴。
穩(wěn)定排序
在這里，我們需要的實(shí)現(xiàn)一個(gè)穩(wěn)定排序寻拂。假設(shè)我們排序的是這樣的數(shù)組：[ { id: 21, value: 3 }, { id: 15, value: 3 }... ]程奠，基于元素的value屬性對(duì)數(shù)組排序，那么僅僅是以上的操作就不能滿足要求了：因?yàn)樵谟?jì)數(shù)數(shù)組中我們只能對(duì)value計(jì)數(shù)祭钉，卻無(wú)法保留元素的整體信息瞄沙。同時(shí)我們想要的是一個(gè)穩(wěn)定排序算法，這意味著，若在原數(shù)組中元素a和b有相同的value距境，且a出現(xiàn)在b的左側(cè)申尼，那么在排序之后，我們?nèi)韵Ｍ?code>a出現(xiàn)在b的左側(cè)垫桂。
于是我們首先對(duì)計(jì)數(shù)數(shù)組進(jìn)行一番操作：
這里我們將計(jì)數(shù)數(shù)組每一位的值师幕，變?yōu)樽髠?cè)（包括自身所有計(jì)數(shù)的累加），例如第0位為1诬滩，第1位為1 + 1 = 2霹粥，第2位為1 + 1 + 2 = 4等。轉(zhuǎn)換之后第k位（最后一位）的值應(yīng)當(dāng)為原數(shù)組的長(zhǎng)度疼鸟。
如圖所示后控，我們從數(shù)組右側(cè)開始掃描數(shù)組，逐一處理：這里為了便于描述空镜，我們先關(guān)注于每當(dāng)遇到元素2時(shí)該如何處理浩淘。
首先我們來(lái)思考，計(jì)數(shù)數(shù)組中2所對(duì)應(yīng)的值4代表了什么吴攒。這里代表了原數(shù)組中不大于2的元素共有4個(gè)张抄，那么當(dāng)我們從右側(cè)開始掃描這個(gè)數(shù)組時(shí)候，遇到的第一個(gè)元素2洼怔，就應(yīng)當(dāng)出現(xiàn)在排序數(shù)組下標(biāo)為4 - 1 = 3的位置上署惯。當(dāng)我們繼續(xù)掃描遇到下一個(gè)元素2的時(shí)候，自然應(yīng)該把它放到第一個(gè)2的左側(cè)茴厉。
因此泽台，我們從右側(cè)開始掃描原數(shù)組什荣，對(duì)每一個(gè)元素都通過(guò)計(jì)數(shù)數(shù)組獲得它應(yīng)該被放置到的位置矾缓，同時(shí)將計(jì)數(shù)數(shù)組中相應(yīng)的值-1。直到原數(shù)組掃描完成稻爬，我們也就取得了排序后的數(shù)組嗜闻。
代碼示例（js）
const sort = (arr) => {
const max = getMax(arr)
const counters = Array(max).fill(0)
arr.forEach((item) => {
counters[item - 1]++
})
counters.forEach((item, index) => {
if (index !== 0) {
counters[index] += counters[index - 1]
}
})
const rtn = Array(arr.length)
for (let i = arr.length - 1; i >= 0; i--) {
const item = arr[i]
const pos = counters[item - 1] - 1
rtn[pos] = item
counters[item - 1] = pos
}
return rtn
}
小結(jié)
計(jì)數(shù)排序是一種線性時(shí)間排序，即Θ(n)桅锄。當(dāng)然這里也有個(gè)問(wèn)題：如果數(shù)組中的最大元素較大琉雳，我們需要?jiǎng)?chuàng)造一個(gè)巨大的計(jì)數(shù)數(shù)組，空間成本太高友瘤。對(duì)于這一問(wèn)題翠肘，接下來(lái)我們將介紹基數(shù)排序。
