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)文章
js實(shí)現(xiàn)表單及時(shí)驗(yàn)證功能 用戶信息立即驗(yàn)證
這篇文章主要為大家詳細(xì)介紹了js實(shí)現(xiàn)表單及時(shí)驗(yàn)證功能，在輸入后就可以立即驗(yàn)證，含用戶類(lèi)型,性別,愛(ài)好等驗(yàn)證,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-09-09
Javascript 生成無(wú)限下拉列表實(shí)現(xiàn)代碼
js生成無(wú)線下拉列表的實(shí)現(xiàn)代碼。2009-03-03
本文給大家通過(guò)3個(gè)方法向大家展示了javascript中的setTimeout的使用，非常的簡(jiǎn)單，有需要的小伙伴可以參考下。2015-07-07
Vue的插槽（Slot）是一種可以讓父組件向子組件傳遞內(nèi)容的機(jī)制，這篇文章主要通過(guò)一些簡(jiǎn)單的示例為大家介紹了插槽的具體使用，感興趣的小伙伴可以了解一下2023-06-06
純javascript實(shí)現(xiàn)自動(dòng)發(fā)送郵件
當(dāng)我們發(fā)送郵件時(shí)，可以自定義郵件發(fā)送的時(shí)間，那么使用代碼是如何實(shí)現(xiàn)的呢？下面通過(guò)本篇文章給大家介紹使用純javascript實(shí)現(xiàn)自動(dòng)發(fā)送郵件，感興趣的朋友可以參考下2015-10-10
不錯(cuò)的應(yīng)用，用方向鍵控制小方塊的移動(dòng)2008-09-09
妙用緩存調(diào)用鏈實(shí)現(xiàn)JS方法的重載
方法重載是指在一個(gè)類(lèi)中定義多個(gè)同名的方法，但要求每個(gè)方法具有不同的參數(shù)的類(lèi)型或參數(shù)的個(gè)數(shù)。簡(jiǎn)而言之就是：方法重載就是方法名稱(chēng)重復(fù)，加載參數(shù)不同2018-04-04
下面小編就為大家分享一篇仿京東快報(bào)向上滾動(dòng)的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2017-12-12
這篇文章主要介紹了12種JavaScript常用的MVC框架比較分析,以獨(dú)特的視角分析了12中常見(jiàn)的JavaScript MVC框架各種優(yōu)缺點(diǎn),具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-11-11
JS實(shí)現(xiàn)拖動(dòng)滑塊驗(yàn)證
這篇文章主要為大家詳細(xì)介紹了JS實(shí)現(xiàn)拖動(dòng)滑塊驗(yàn)證，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03