您现在的位置: 万盛学电脑网 >> 程序编程 >> 脚本专题 >> javascript >> 正文

Javascript排序算法之计数排序的实例

作者:佚名    责任编辑:admin    更新时间:2022-06-22

 计数排序是一种高效的线性排序,它通过计算一个集合中元素楚翔的次数来确定集合如何排列,计数排序不需要进行数据的比较,所有他的运行效率前面介绍的都高

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组Count_arr,其中第i个元素是待排序数组Arr中值等于i的元素的个数。然后根据数组Count_arr来将Arr中的元素排到正确的位置。 分为四个步骤: 1.找出待排序的数组中最大和最小的元素 2.统计数组中每个值为i的元素出现的次数,存入数组Count_arr的第i项 3.对所有的计数累加(从Count_arr中的第一个元素开始,每一项和前一项相加) 4.反向遍历原数组:将每个元素i放在新数组的第Count_arr(i)项,每放一个元素就将Count_arr(i)减去1   实例:    代码如下: /**  * 计数排序是一个非基于比较的排序算法,  * 该算法于1954年由 Harold H. Seward 提出。  * 它的优势在于在对一定范围内的整数排序时,  * 它的复杂度为Ο(n+k)(其中k是整数的范围),  * 快于任何比较排序算法。  *  */   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);