學(xué)號(hào)：20021211189? ? ? ?姓名：趙治偉
【嵌牛導(dǎo)讀】計(jì)數(shù)排序（Counting sort）是一種非基于比較的排序算法，其核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中以達(dá)到排序的效果。
【嵌牛鼻子】計(jì)數(shù)排序算法
【嵌牛正文】
給定一組取值范圍為0到9的無序序列：1慰枕、7诉濒、4胀糜、9垢油、0壕探、5飘诗、2与倡、4、7昆稿、3纺座、4，建立一個(gè)長(zhǎng)度為10的計(jì)數(shù)數(shù)組溉潭，值初始化為0
遍歷無序序列净响，將每個(gè)序列元素值對(duì)應(yīng)的計(jì)數(shù)數(shù)組下標(biāo)的元素加1
如：第一個(gè)序列元素為1，則計(jì)數(shù)數(shù)組中下標(biāo)為1的元素加1
第二個(gè)序列元素為7岛抄，計(jì)數(shù)數(shù)組中下標(biāo)為7的元素加1
繼續(xù)遍歷序列别惦，當(dāng)序列遍歷完畢，計(jì)數(shù)數(shù)組的最終狀態(tài)如下：
遍歷計(jì)數(shù)數(shù)組夫椭，輸出計(jì)數(shù)數(shù)組下標(biāo)值掸掸，元素的值是多少，就輸出幾次
輸出結(jié)果如下：0蹭秋、1扰付、2、3仁讨、4羽莺、4、4洞豁、5盐固、7、7丈挟、9
此時(shí)刁卜，元素已是有序的了
// 計(jì)數(shù)排序
function sort(arr) {
? ? // 得到數(shù)列的最大值
? ? let max = arr[0];
? ? for (let item of arr) {
? ? ? ? if (item > max) {
? ? ? ? ? ? max = item;
? ? ? ? }
? ? }
? ? // 初始化數(shù)組
? ? let countArr = [];
? ? for (let i = 0; i <= max; i++) {
? ? ? ? countArr[i] = 0;
? ? }
? ? // 遍歷原始數(shù)組，填充計(jì)數(shù)數(shù)組
? ? for (let item of arr) {
? ? ? ? countArr[item]++;
? ? }
? ? // 遍歷計(jì)數(shù)數(shù)組曙咽，得到排序后結(jié)果
? ? let index = 0;
? ? let sortArr = [];
? ? for (let i = 0; i <= max; i++) {
? ? ? ? for (let j = 0; j < countArr[i]; j++) {
? ? ? ? ? ? sortArr[index++] = i;
? ? ? ? }
? ? }
? ? return sortArr;
}
let arr = [1, 7, 4, 9, 0, 5, 2, 4, 7, 3, 4];
let sortArr = sort(arr);
console.log(sortArr);
在前面的例子中蛔趴，我們以序列的最大值來確定計(jì)數(shù)數(shù)組長(zhǎng)度，假設(shè)有一個(gè)序列83例朱、80孝情、88鱼蝉、90、88箫荡、86魁亦，那么我們創(chuàng)建一個(gè)長(zhǎng)度為91的計(jì)數(shù)數(shù)組，計(jì)數(shù)數(shù)組的0到79位都浪費(fèi)了
我們可以創(chuàng)建一個(gè)長(zhǎng)度為90-80+1=11（最大值-最小值+1）的計(jì)數(shù)數(shù)組菲茬，計(jì)數(shù)數(shù)組的偏移量為序列的最小值80
如圖：計(jì)數(shù)數(shù)組下標(biāo)0對(duì)應(yīng)序列80吉挣，下標(biāo)1對(duì)應(yīng)序列81，以此類推
此外婉弹，我們前面的例子中睬魂，我們?cè)谛陆ǖ挠?jì)數(shù)數(shù)組中記錄序列中每個(gè)元素的數(shù)量，如果序列有相同的元素镀赌，則在輸出時(shí)氯哮，無法保證元素原來的排序，是一種不穩(wěn)定的排序算法商佛，可通過優(yōu)化喉钢，將其改為穩(wěn)定排序算法
以序列83、80良姆、88肠虽、90、88玛追、86為例税课，首先填充計(jì)數(shù)數(shù)組
將計(jì)數(shù)數(shù)組從第二個(gè)元素開始，每個(gè)元素都加上前面所有元素的和痊剖，此時(shí)韩玩，計(jì)數(shù)數(shù)組的值表示的是元素在序列中的排序
接下來我們創(chuàng)建輸出數(shù)組，長(zhǎng)度與待排序序列一致陆馁，從后往前遍歷待排序序列
首先找颓，遍歷最后一個(gè)元素86，我們?cè)谟?jì)數(shù)數(shù)組中找到86對(duì)應(yīng)的值為3叮贩，則在輸出數(shù)組的第3位（下標(biāo)為2）填入86击狮，計(jì)數(shù)數(shù)組86對(duì)應(yīng)的值減1，既當(dāng)前的86排序是3益老，下次遇到86則排序是2
接著帘不，遍歷下一個(gè)元素88，在計(jì)數(shù)數(shù)組中找到88對(duì)應(yīng)的值為5杨箭，在輸出數(shù)組的第5位（下標(biāo)為4）填入88，計(jì)數(shù)數(shù)組88對(duì)應(yīng)的值減1
然后储狭，遍歷下一個(gè)元素90互婿，在計(jì)數(shù)數(shù)組中找到90對(duì)應(yīng)的值為6捣郊，在輸出數(shù)組的第6位（下標(biāo)為5）填入90，計(jì)數(shù)數(shù)組90對(duì)應(yīng)的值減1
繼續(xù)遍歷下一個(gè)元素88慈参，在計(jì)數(shù)數(shù)組中找到88對(duì)應(yīng)的值為4呛牲，在輸出數(shù)組的第4位（下標(biāo)為3）填入88，計(jì)數(shù)數(shù)組88對(duì)應(yīng)的值減1
以此類推驮配，將所有元素遍歷完娘扩，填入輸出數(shù)組
原序列第3位、第5位均為88壮锻，從上面的步驟我們可以看到琐旁，在第二步，第5位的88填入輸出數(shù)組的第5位猜绣，在第四步灰殴，第3位的88填入輸出數(shù)組的第4位，沒有改變?cè)蛄邢嗤氐捻樞?/p>
優(yōu)化后代碼如下：
// 計(jì)數(shù)排序優(yōu)化
function sort(arr) {
? ? // 得到數(shù)列的最大值掰邢、最小值牺陶，并計(jì)算計(jì)數(shù)數(shù)組長(zhǎng)度
? ? let max = arr[0];
? ? let min = arr[0];
? ? for (let item of arr) {
? ? ? ? if (item > max) {
? ? ? ? ? ? max = item;
? ? ? ? }
? ? ? ? if (item < min) {
? ? ? ? ? ? min = item;
? ? ? ? }
? ? }
? ? let length = max - min + 1;
? ? // 初始化計(jì)數(shù)數(shù)組
? ? let countArr = [];
? ? for (let i = 0; i < length; i++) {
? ? ? ? countArr[i] = 0;
? ? }
? ? // 遍歷原始數(shù)組，填充計(jì)數(shù)數(shù)組
? ? for (let item of arr) {
? ? ? ? countArr[item - min]++;
? ? }
? ? // 計(jì)數(shù)數(shù)組形變辣之，后面的元素等于前面的元素之和
? ? let sum = 0;
? ? for (let i = 0; i < length; i++) {
? ? ? ? sum += countArr[i];
? ? ? ? countArr[i] = sum;
? ? }
? ? console.log(11111111, countArr);
? ? // 倒序遍歷計(jì)數(shù)數(shù)組掰伸，從計(jì)數(shù)數(shù)組中找到正確位置，輸入到輸出數(shù)組
? ? let sortArr = [];
? ? for (let i = arr.length - 1; i >= 0; i--) {
? ? ? ? sortArr[countArr[arr[i] - min] - 1] = arr[i];
? ? ? ? countArr[arr[i] - min]--;
? ? ? ? console.log(arr[i], countArr, sortArr);
? ? }
? ? return sortArr;
}
let arr = [83, 80, 88, 90, 88, 86];
let sortArr = sort(arr);
console.log(sortArr);
計(jì)數(shù)排序算法遍歷了3次原始數(shù)組怀估，一次計(jì)數(shù)數(shù)組狮鸭，所以算法的時(shí)間復(fù)雜度是O(N+M)
計(jì)數(shù)排序算法排序過程中新建了一個(gè)計(jì)數(shù)數(shù)組和一個(gè)輸出數(shù)組，所以算法的空間復(fù)雜度是O(N+M)
優(yōu)化后的計(jì)數(shù)排序算法在排序過程中奏夫，相同元素的前后順序不會(huì)發(fā)生改變怕篷，是一種穩(wěn)定排序算法
當(dāng)待排序序列的最大值和最小值差值特別大時(shí)，不適合使用計(jì)數(shù)排序算法
當(dāng)待排序序列的值不是整數(shù)時(shí)酗昼，不適合使用計(jì)數(shù)排序算法
