排序

• 排序：把某個(gè)亂序的數(shù)組變成升序或降序的數(shù)組 (這里用數(shù)組來做舉例)

計(jì)數(shù)排序

• 核心思想：通過計(jì)數(shù)而非比較來進(jìn)行排序，借助數(shù)組下標(biāo)本身就是有序的原理實(shí)現(xiàn)
• 適用范圍：較小的非負(fù)整數(shù)序列和最小值和最大值之間的數(shù)字范圍比較合適
• 基數(shù)排序需要新增一個(gè)計(jì)數(shù)數(shù)組(待累計(jì)數(shù)組)
  • 計(jì)數(shù)數(shù)組：即新的臨時(shí)的初始化數(shù)組用于計(jì)數(shù)，需要找到原始數(shù)組中最大的值，再加1，才是這個(gè)數(shù)組的長度，存儲(chǔ) [0 ~ max]
  • 累計(jì)數(shù)組：是由計(jì)數(shù)數(shù)組計(jì)算后得到的，下標(biāo)是原數(shù)組的值，元素值是累計(jì)的個(gè)數(shù)，即重復(fù)的個(gè)數(shù)

算法實(shí)現(xiàn)

1 ）基礎(chǔ)版本

function countSort(list: number[]) {
	const len: number = list.length;
	if (len < 2) return;
	// 獲取最大值
	// const max = Math.max.apply(null, list);
	const max: number = Math.max(...list);
	// 初始化計(jì)數(shù)數(shù)組
	const countList: number[] = new Array(max + 1).fill(0); // 數(shù)組大小，存放[0~max]
	// 對(duì)原數(shù)組的數(shù)據(jù)在計(jì)數(shù)數(shù)組中累計(jì)，原數(shù)組的值是計(jì)數(shù)數(shù)組的下標(biāo)
	let i: number;
	for(i = 0; i < len; i++) countList[list[i]]++; // 遍歷完成后計(jì)數(shù)數(shù)組就變成了累計(jì)數(shù)組
	// 基于累計(jì)數(shù)組生成排好序的數(shù)組，這里利用了下標(biāo)即是有序的原理
	i = 0; // 重新使用i
	for(let j: number = 0; j < max + 1; j++) {
    	// 內(nèi)層循環(huán)不會(huì)到n, 一般是常數(shù)級(jí)別的，但是這樣寫似乎也不是太好，嵌套會(huì)增加時(shí)間復(fù)雜度
		for (let k: number = 0; k < countList[j]; k++) list[i++] = j; // 這里j就是下標(biāo)，其實(shí)就是原數(shù)組的值
	}
}

const list = [2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
countSort(list);
console.log(list); // [1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

2 ）優(yōu)化版本：優(yōu)化時(shí)間復(fù)雜度(空間換時(shí)間)

function countSort(list: number[]): number[] {
	const len: number = list.length;
	if (len < 2) return list;
	// 獲取最大值和最小值
	// const max = Math.max.apply(null, list);
	// const min = Math.min.apply(null, list);
	const max: number = Math.max(...list);
	const min: number = Math.min(...list);
	// 初始化計(jì)數(shù)數(shù)組
	const countList: number[] = new Array(max - min + 1).fill(0);
	// 對(duì)原數(shù)組的數(shù)據(jù)在計(jì)數(shù)數(shù)組中累計(jì)，原數(shù)組的值是計(jì)數(shù)數(shù)組的下標(biāo)
	for(let i: number = 0; i < len; i++) countList[list[i] - min]++; // 遍歷完成后計(jì)數(shù)數(shù)組就變成了累計(jì)數(shù)組
	// 基于累計(jì)數(shù)組生成排好序的數(shù)組，這里利用了下標(biāo)即是有序的原理
	let result: number[] = [];
	for(let j: number = 0; j < max + 1; j++) {
		if (!countList[j]) continue;
		countList[j] > 1 ? (result = result.concat(new Array(countList[j]).fill(j + min))) : result.push(j + min);
	}
	return result; // 替換
}

const list: number[] = [102, 103, 108, 107, 101, 102, 102, 102, 107, 103, 109, 108, 102, 101, 104, 102, 104, 106, 109, 102];
const result: number[] = countSort(list);
console.log(result); // [101, 101, 102, 102, 102, 102, 102, 102, 102, 103, 103, 104, 104, 106, 107, 107, 108, 108, 109, 109]

3 ）優(yōu)化版本：優(yōu)化時(shí)間復(fù)雜度(空間換時(shí)間) + 優(yōu)化存儲(chǔ)空間

function countSort(list: number[]) {
	const len: number = list.length;
	if (len < 2) return list;
	// 獲取最大值和最小值
	const max: number = Math.max(...list);
	const min: number = Math.min(...list);
	// 初始化計(jì)數(shù)數(shù)組
	const countList: number[] = new Array(max - min + 1).fill(0);
	// 對(duì)原數(shù)組的數(shù)據(jù)在計(jì)數(shù)數(shù)組中累計(jì)，原數(shù)組的值是計(jì)數(shù)數(shù)組的下標(biāo)
	for(let i: number = 0; i < len; i++) countList[list[i] - min]++; // 遍歷完成后計(jì)數(shù)數(shù)組就變成了累計(jì)數(shù)組
	// 基于累計(jì)數(shù)組生成排好序的數(shù)組，這里利用了下標(biāo)即是有序的原理
	let str: string = ''; // 用字符串來處理
	for(let j: number = 0; j < max - min + 1; j++) {
		if (!countList[j]) continue;
		str += countList[j] > 1 ? ((j + min) + ',').repeat(countList[j]) : (j + min) + ',';
	}
	str = str.substring(0, str.length - 1); // 最后一個(gè) , 是多余的
	return str.split(',').map(item => Number(item));
}

const list: number[] = [102, 103, 108, 107, 101, 102, 102, 102, 107, 103, 109, 108, 102, 101, 104, 102, 104, 106, 109, 102];
const result: number[] = countSort(list);
console.log(result); // [101, 101, 102, 102, 102, 102, 102, 102, 102, 103, 103, 104, 104, 106, 107, 107, 108, 108, 109, 109]

4 ）優(yōu)化版本：優(yōu)化時(shí)間復(fù)雜度(累計(jì)數(shù)組變位置數(shù)組，基于差值和位置來對(duì)應(yīng)順序)文章來源地址http://www.zghlxwxcb.cn/news/detail-738400.html

function countSort(list: number[]) {
	const len: number = list.length;
	if (len < 2) return;
	// 獲取最大值和最小值
	const max: number = Math.max(...list);
	const min: number = Math.min(...list);
	// 初始化計(jì)數(shù)數(shù)組
	const countList: number[] = new Array(max - min + 1).fill(0);
	// 初始化目標(biāo)數(shù)組
	const result: number[] = new Array(len);
	// 對(duì)原數(shù)組的數(shù)據(jù)在計(jì)數(shù)數(shù)組中累計(jì)，原數(shù)組的值是計(jì)數(shù)數(shù)組的下標(biāo)
	for(let i: number = 0; i < len; i++) countList[list[i] - min]++; // 遍歷完成后計(jì)數(shù)數(shù)組就變成了累計(jì)數(shù)組
	// 計(jì)算位置: 由上面的累計(jì)結(jié)果，計(jì)算累加后的位置, countList數(shù)組從累計(jì)數(shù)組，變成了位置數(shù)組
	for(let j: number = 1; j < max - min + 1; j++) {
		countList[j] += countList[j - 1];
	}
	// 根據(jù)累加后的位置, 將原數(shù)組中的數(shù)據(jù)按照位置進(jìn)行分配，就得到排好序的數(shù)組，備注：數(shù)據(jù)可能重復(fù)，使用過的數(shù)據(jù)記得-1，從后向前遍歷更好理解
	for (let k: number = len - 1; k >= 0; k--) {
		const currentIndex = countList[list[k] - min] - 1;
		result[currentIndex] = list[k]; // 將原數(shù)組的當(dāng)前元素整合到 result數(shù)組對(duì)應(yīng)的位置之中
		countList[list[k] - min] --; // 使用一次后，累計(jì)的數(shù)量自減，防止重復(fù)使用導(dǎo)致錯(cuò)誤
	}
	list.splice(0, len, ...result); // 優(yōu)化下方式，不用return, 直接替換
}

const list: number[] = [102, 103, 108, 107, 101, 102, 102, 102, 107, 103, 109, 108, 102, 101, 104, 102, 104, 106, 109, 102];
countSort(list);
console.log(list); // [101, 101, 102, 102, 102, 102, 102, 102, 102, 103, 103, 104, 104, 106, 107, 107, 108, 108, 109, 109]

總結(jié)

• 計(jì)數(shù)排序的適用范圍有限：最優(yōu)版時(shí)間復(fù)雜度可降低到 O(n), 是最快的排序算法, 但是有兩個(gè)前提需要滿足
  • 1）需要排序的元素必須是非負(fù)整數(shù)(下標(biāo)不能是負(fù)數(shù)和小數(shù))
    • 如果是小數(shù)，需要將全部元素同等擴(kuò)大到整數(shù)，之后再回歸到小數(shù)
    • 一般不考慮這種小數(shù)場景
  • 2）排序元素的取值要在一定范圍內(nèi)，并且比較集中(量大，范圍小)
• 滿足以上兩個(gè)條件，才能最大發(fā)揮出計(jì)數(shù)排序的優(yōu)勢(shì), 否則不適用
• 計(jì)數(shù)排序的缺點(diǎn)
  • 基礎(chǔ)版空間浪費(fèi)，優(yōu)化版解決了這個(gè)問題
  • 將數(shù)組長度定為 max-min+1, 即不僅要找出最大值，還要找出最小值
• 缺點(diǎn)彌補(bǔ)：根據(jù)兩者的差來確定計(jì)數(shù)數(shù)組的長度則可彌補(bǔ)之
• 計(jì)數(shù)排序是非常穩(wěn)定的排序算法，但是適用場景確實(shí)有限
• 計(jì)數(shù)排序是一種桶排序的思想

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法之排序: 計(jì)數(shù)排序 (Javascript版)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！