資訊專欄INFORMATION COLUMN
摘要：計(jì)數(shù)排序首先我們要對(duì)計(jì)數(shù)排序有一個(gè)正確的認(rèn)識(shí)計(jì)數(shù)排序是用于確定范圍的整數(shù)的線性時(shí)間排序算法這一句話我們就可以知道計(jì)數(shù)排序該如何用了處理數(shù)據(jù)確定范圍內(nèi)的整數(shù)特點(diǎn)快線性時(shí)間其數(shù)據(jù)如下最佳情況最差情況平均情況計(jì)數(shù)排序的步驟如下查找待排序數(shù)組中最大
計(jì)數(shù)排序
首先我們要對(duì)計(jì)數(shù)排序有一個(gè)正確的認(rèn)識(shí),計(jì)數(shù)排序是用于確定范圍的整數(shù)的線性時(shí)間排序算法,這一句話我們就可以知道計(jì)數(shù)排序該如何用了.
處理數(shù)據(jù):確定范圍內(nèi)的整數(shù)
特點(diǎn):快(線性時(shí)間)
其數(shù)據(jù)如下:
最佳情況：T(n) = O(n+k)
最差情況：T(n) = O(n+k)
平均情況：T(n) = O(n+k)
計(jì)數(shù)排序的步驟如下
查找待排序數(shù)組中最大和最小的元素
統(tǒng)計(jì)每個(gè)值為i的元素的出現(xiàn)次數(shù)
對(duì)所有計(jì)數(shù)開始累加(從min開始,每一項(xiàng)和前一項(xiàng)相加)
反向填充目標(biāo)數(shù)組,將每個(gè)元素i放在新數(shù)組的第C[i]項(xiàng),每放一個(gè)元素,計(jì)數(shù)-1.
JS代碼如下:
function countingSort(arr){
var len = arr.length,
Result = [],
Count = [],
min = max = arr[0];
console.time("countingSort waste time:");
/*查找最大最小值,并將arr數(shù)置入Count數(shù)組中,統(tǒng)計(jì)出現(xiàn)次數(shù)*/
for(var i = 0;i= arr[i] ? max : arr[i];
}
/*從最小值->最大值,將計(jì)數(shù)逐項(xiàng)相加*/
for(var j = min;j=0;k--){
/*Result[位置] = arr數(shù)據(jù)*/
Result[Count[arr[k]] - 1] = arr[k];
/*減少Count數(shù)組中保存的計(jì)數(shù)*/
Count[arr[k]]--;
/*顯示Result數(shù)組每一步詳情*/
console.log(Result);
}
console.timeEnd("countingSort waste time:");
return Result;
}
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(countingSort(arr));
運(yùn)行結(jié)果為:
[ , , , , , , , , , , , , , 48 ]
[ , , , , , , , , , , , , , 48, 50 ]
[ , , , , , 19, , , , , , , , 48, 50 ]
[ , , 4, , , 19, , , , , , , , 48, 50 ]
[ , , 4, , , 19, , , , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, , , , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, , 27, , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, 26, 27, , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, 26, 27, 36, , , 46, , 48, 50 ]
[ 2, , 4, , 15, 19, 26, 27, 36, , , 46, , 48, 50 ]
[ 2, , 4, , 15, 19, 26, 27, 36, , , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, , , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, 38, , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]
[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]
countingSort waste time:: 14ms
[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]
仔細(xì)看代碼就知道其實(shí)過程很簡單,但是個(gè)人認(rèn)為編碼時(shí)的關(guān)鍵在于理解最后反向填充時(shí)的操作.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/86617.html
摘要：將大的先放在后面，再下一次可以把相同大的放在上一次的之前，順序改變。 之前介紹的排序算法： 【算法】插入排序——希爾排序+直接插入排序_Rinne’s blog-C...
本篇有7k+字, 系統(tǒng)梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復(fù)雜的排序?qū)崿F(xiàn)，如果喜歡請(qǐng)點(diǎn)贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導(dǎo)讀 排序算法可以稱得上是我的盲點(diǎn), 曾幾何時(shí)當(dāng)我知道Chrome的Array.prototype.sort使用了快速排序時(shí), 我的內(nèi)心是奔潰的(啥是快排, 我只知道...
摘要：代碼實(shí)現(xiàn)六堆排序算法簡介堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。九計(jì)數(shù)排序算法簡介計(jì)數(shù)排序是一種穩(wěn)定的排序算法。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。 贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介 插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...
摘要：結(jié)構(gòu)型模式適配器模式橋接模式裝飾模式組合模式外觀模式享元模式代理模式。行為型模式模版方法模式命令模式迭代器模式觀察者模式中介者模式備忘錄模式解釋器模式模式狀態(tài)模式策略模式職責(zé)鏈模式責(zé)任鏈模式訪問者模式。 主要版本 更新時(shí)間 備注 v1.0 2015-08-01 首次發(fā)布 v1.1 2018-03-12 增加新技術(shù)知識(shí)、完善知識(shí)體系 v2.0 2019-02-19 結(jié)構(gòu)...
閱讀 1833·2021-11-18 13:21
閱讀 1966·2021-10-18 13:30
閱讀 1551·2021-10-12 10:13
閱讀 922·2021-10-09 09:43
閱讀 5436·2021-09-22 15:13
閱讀 3595·2021-08-11 10:22
閱讀 947·2019-08-30 13:46
閱讀 3527·2019-08-30 13:21
