Javascript排序算法之計(jì)數(shù)排序的實(shí)例
更新時(shí)間：2014年04月05日 10:10:33 作者：
計(jì)數(shù)排序是一種高效的線性排序，它通過(guò)計(jì)算一個(gè)集合中元素楚翔的次數(shù)來(lái)確定集合如何排列，計(jì)數(shù)排序不需要進(jìn)行數(shù)據(jù)的比較，所有他的運(yùn)行效率前面介紹的都高
計(jì)數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法。計(jì)數(shù)排序使用一個(gè)額外的數(shù)組Count_arr，其中第i個(gè)元素是待排序數(shù)組Arr中值等于i的元素的個(gè)數(shù)。然后根據(jù)數(shù)組Count_arr來(lái)將Arr中的元素排到正確的位置。
分為四個(gè)步驟：
1.找出待排序的數(shù)組中最大和最小的元素
2.統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組Count_arr的第i項(xiàng)
3.對(duì)所有的計(jì)數(shù)累加（從Count_arr中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）
4.反向遍歷原數(shù)組：將每個(gè)元素i放在新數(shù)組的第Count_arr(i)項(xiàng)，每放一個(gè)元素就將Count_arr(i)減去1
實(shí)例：
復(fù)制代碼 代碼如下:
/**
* 計(jì)數(shù)排序是一個(gè)非基于比較的排序算法，
* 該算法于1954年由 Harold H. Seward 提出。
* 它的優(yōu)勢(shì)在于在對(duì)一定范圍內(nèi)的整數(shù)排序時(shí)，
* 它的復(fù)雜度為Ο(n+k)（其中k是整數(shù)的范圍），
* 快于任何比較排序算法。
*
*/
function countSort(arr, min, max) {
var i, z = 0, count = [];
for (i = min; i <= max; i++) {
count[i] = 0;
}
for (i=0; i < arr.length; i++) {
count[arr[i]]++;
}
for (i = min; i <= max; i++) {
while (count[i]-- > 0) {
arr[z++] = i;
}
}
return arr;
}
// test
var i, arr = [];
for (i = 0; i < 100; i++) {
arr.push(Math.floor(Math.random() * (141)));
}
countSort(arr, 0, 140);
相關(guān)文章
基于JavaScript實(shí)現(xiàn)文件共享型網(wǎng)站
Any?Share?是一種簡(jiǎn)單、輕量、快速的文件共享服務(wù)。使用?Javascript?編寫，并搭建在?Firebase?平臺(tái)。本文將利用它實(shí)現(xiàn)創(chuàng)建文件共享型網(wǎng)站，感興趣的可以了解一下2022-11-11
js實(shí)現(xiàn)鼠標(biāo)點(diǎn)擊左上角滑動(dòng)菜單效果代碼
這篇文章主要介紹了js實(shí)現(xiàn)鼠標(biāo)點(diǎn)擊左上角滑動(dòng)菜單效果代碼,涉及JavaScript基于鼠標(biāo)事件動(dòng)態(tài)變換頁(yè)面元素樣式的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了js replace 全局替換的操作方法，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-06-06
本文針對(duì)目前常見(jiàn)的面試題，僅提供了相應(yīng)的核心原理及思路，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2019-07-07
JS實(shí)現(xiàn)禁止高頻率連續(xù)點(diǎn)擊的方法【基于ES6語(yǔ)法】
這篇文章主要介紹了JS實(shí)現(xiàn)禁止高頻率連續(xù)點(diǎn)擊的方法,通過(guò)事件監(jiān)聽(tīng)結(jié)合定時(shí)器實(shí)現(xiàn)針對(duì)高頻率點(diǎn)擊的限制操作,該功能基于ES6語(yǔ)法實(shí)現(xiàn),需要的朋友可以參考下2017-04-04
這篇文章主要介紹了微信小程序中的生命周期與生命周期函數(shù)的介紹，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
制作網(wǎng)頁(yè)的過(guò)程中，你有時(shí)候需要知道某個(gè)元素在網(wǎng)頁(yè)上的確切位置，在接下來(lái)的文章中為大家介紹下使用js是如何實(shí)現(xiàn)的2013-12-12
本文對(duì)JavaScript事件加載進(jìn)行了一些延伸思考。加載多個(gè)事件時(shí)，使用window.onload可能會(huì)導(dǎo)致一些不便，而通過(guò)偵聽(tīng)器等方法，則可以解決這些問(wèn)題。2009-12-12
JS中setTimeout的巧妙用法前端函數(shù)節(jié)流
這篇文章主要介紹了JS中setTimeout的巧妙用法前端函數(shù)節(jié)流 的相關(guān)資料,需要的朋友可以參考下2016-03-03
B/S開(kāi)發(fā)中常用javaScript技術(shù)與代碼
B/S開(kāi)發(fā)中常用javaScript技術(shù)與代碼...2007-03-03