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

2015-01-31  来源:本站原创  分类:javascript技巧  人气:0 

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

计数排序(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);
相关文章
  • Javascript排序算法之计数排序的实例 2015-01-31

    计数排序是一种高效的线性排序,它通过计算一个集合中元素楚翔的次数来确定集合如何排列,计数排序不需要进行数据的比较,所有他的运行效率前面介绍的都高 计数排序(Counting sort)是一种稳定的排序算法.计数排序使用一个额外的数组Count_arr,其中第i个元素是待排序数组Arr中值等于i的元素的个数.然后根据数组Count_arr来将Arr中的元素排到正确的位置. 分为四个步骤: 1.找出待排序的数组中最大和最小的元素 2.统计数组中每个值为i的元素出现的次数,存入数组Count_arr的

  • 排序算法笔记:计数排序 CountingSort in java 2014-01-04

    /** * 计数排序 * 简述: * 创建一个临时数组temp[max],max>=max(array).先统计array[i]的个数于temp[array[i]]上,再通过temp[]确定每一个数字的位置(算出有m个比n小的,则n就在m+1上),最后将数据串与result上. * 时间复杂度: * 当k=O(n)时,为O(n) * 空间复杂度: * O(n) * 优点: * 时间复杂度几乎为最低 * 缺点: * 对数组内容要求较多:1.全为自然数;2.若数字太大,则需要过多额外空间. * 可改

  • 排序算法笔记:桶排序 BucketSort in java 2014-01-12

    /** * 桶排序: * 简述: * 简单说来就是分块儿排序.假设输入数组为均匀分布,然后将数据分为n段--称之为桶,将全部数据依次放入桶中,再通过递归将桶中数字取出再细分,或者利用其他排序算法,将局部数字排序,最后将桶按照区间大小重新串起即可. * 时间复杂度: * * 空间复杂度: * * 递归式: * * 优点: * 如已知数据连续.数据集中在某一个区间,可以将该算法视为一个较为高效的算法. * 缺点: * 算法复杂度主要取决于step的大小(也就是桶的宽度,即区间大小),以及用于桶内排序

  • 排序算法笔记:希尔排序 ShellSort in java 2014-01-12

    /** * 希尔排序 * 简述: * 希尔排序是插入排序的一种改进.将需要排序的序列划分成为若干个较小的子序列,对子序列进行插入排序,通过则插入排序能够使得原来序列成为基本有序. * 时间复杂度: * * 空间复杂度: * * 优点: * * 缺点: * * 可改进: * * @author CheN * */ public class ShellSort { /** * 正序 * @param array * @return */ public static int[] asc(int[] a

  • 排序算法笔记:选择排序 SelectionSort in java 2014-01-12

    /** * 选择排序 * 简述: * 从array[0]开始,与后面所有位进行比较,将最小的放置于此,再继续进行array[i]与它后面的位比较 * 时间复杂度: * Θ(n^2) * 空间复杂度: * O(1) * 优点: * * 缺点: * * 可改进: * * @author CheN * */ public class SelectionSort { public static int[] asc( int[] array ){ for( int i = 0 ; i < array.le

  • 常用排序算法之JavaScript实现 2014-03-23

    笔试面试经常涉及各种算法,本文简要介绍常用的一些算法,并用JavaScript实现. 1.插入排序 1)算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间. 2)算法描述和实现 一般来说,插入排序都采

  • 几种排序算法 2011-05-12

    高效率排序算法 实用排序算法(复杂度小于等于O(n^2))中效率最低但实现并不是最简单的的两个,C.C++教材却总喜欢拿来大讲特讲,非常不利于初学者养成"程序效率"的思维. 实际上,各种排序算法里,除了堆排序实现较为复杂外,从代码量的角度,大多数算法都不比冒泡.选择算法复杂多少. 举几个高速的排序算法的例子,这些才适合进入教材 鸽巢排序,排序字节串.宽字节串最快的排序算法,计数排序的变种(将计数缓冲区大小固定,少一次遍历开销),速度是STL中std::sort的20多倍,更重要的是实现

  • Javascript中的常见排序算法 2013-10-12

    用JavaScript实现的常见排序算法:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序. 具体代码及比较如下所示: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http

  • PHP四种基本排序算法示例 2014-05-05

    这篇文章主要介绍了PHP四种基本排序算法示例,本文用一个实例讲解冒泡排序法.快速排序法.选择排序法.插入排序法的使用,需要的朋友可以参考下 许多人都说算法是程序的核心,算法的好坏决定了程序的质量.作为一个初级phper,虽然很少接触到算法方面的东西.但是对于基本的排序算法还是应该掌握的,它是程序开发的必备工具.这里介绍冒泡排序,插入排序,选择排序,快速排序四种基本算法,分析一下算法的思路. 前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序. $

  • 算法之排序算法的算法思想和使用场景总结 2014-05-26

    这篇文章主要介绍了算法之排序算法的算法思想和使用场景总结,本文讲解了插入排序.交换排序.选择排序等几大类排序算法的特点.思想和使用场景,需要的朋友可以参考下 1. 概述 排序算法是计算机技术中最基本的算法,许多复杂算法都会用到排序.尽管各种排序算法都已被封装成库函数供程序员使用,但了解排序算法的思想和原理,对于编写高质量的软件,显得非常重要. 本文介绍了常见的排序算法,从算法思想,复杂度和使用场景等方面做了总结. 2. 几个概念 (1)排序稳定:如果两个数相同,对他们进行的排序结果为他们的相对顺

  • 让程序员抓狂的排序算法教学视频 2014-03-08

    罗马尼亚是一个爱跳舞的民族,如果你看过罗马尼亚老电影<奇普里安.博隆贝斯库>,那欢快悠扬的舞曲之炽热呵,非把你融化不可! 罗马尼亚人爱跳舞,不仅体现在电影和节日中,你会发现舞蹈无处不在,即使是大学里的计算机课程中的排序算法教学,也被用舞蹈的形式表现出来. 罗马尼亚Tirgu Mures地区的Sapientia大学就制作了一系列用民族舞蹈形式表现的各种排序算法的工作原理.下面就是这些视频. 舞跳的很好,但教学效果如何,我很难评判,至少让我对这几种排序算法的效率产生了严重的怀疑. 排序算法:选择排

  • 白话排序算法(选择,插入,冒泡) 2012-03-26

    排序算法是算法中的基础,今天我来用自己的话说下三种最基本的算法,理解了这三种基本的算法就可以进一步学习怎么优化排序算法了.呵呵,废话不多说,咱们开始. 简单选择排序算法: 简单选择排序的基本思想是:一次选定数组中的一个数,记下当前位置并假设它是从当前位置开始后面数中的最小数min=i,从这个数的下一个数开始扫描直到最后一个数,并记录下最小数的位置min,扫描结束后如果min不等于i,说明假设错误,则交换min与i位置上数.(也即:每次从数列中找出一个最小的数放到最前面来,再从剩下的n-1个数中选

  • 计数排序实现 2014-03-03

    计数排序实现: 计数排序属于稳定排序,时间复杂度为O(n), 主要的思路: 找出数组中小于其中某个元素element的个数i,那么该element就应该位于数组的第i+1个位置: 比如: A为待排序数组,C为计数数组(下标对应A的各元素值,下标值为该元素值出现的个数),B存放排序后的数组,实现代码: /** * 计数排序 * @param A 待排序数组 * @param B 对应A排序后的数组, * @param k A数组中最大元素 */ public static void countin

  • 常见的排序算法及其java实现 2015-03-14

    概括 排序大的分类可以分为两种:内排序和外排序.在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序.下面讲的排序都是属于内排序. 内排序有可以分为以下几类: (1).插入排序:插入排序.希尔排序. (2).选择排序:选择排序.堆排序. (3).交换排序:冒泡排序.快速排序. (4).归并排序 (5).基数排序 时间复杂度.空间复杂度以及稳定性如下表: 相关概念 时间复杂度:算法的时间复杂度是一个函数,它定量描述了该算法的运行时间. (1)时间频度 一个算法执

  • python算法学习之计数排序实例 2014-03-24

    本代码介绍了python算法学习中的计数排序实例,代码大家参考使用吧 python算法学习之计数排序实例 # -*- coding: utf-8 -*- def _counting_sort(A, B, k): """计数排序,伪码如下: COUNTING-SORT(A, B, k) 1 for i ← 0 to k // 初始化存储区的值 2 do C[i] ← 0 3 for j ← 1 to length[A] // 为各值计数 4 do C[A[j]] ← C[A[j

  • python计数排序和基数排序算法实例 2014-11-15

    这篇文章主要介绍了python计数排序和基数排序算法实例,需要的朋友可以参考下 一.计数排序 计数排序(Counting sort)是一种稳定的排序算法 算法的步骤如下: 找出待排序的数组中最大和最小的元素 统计数组中每个值为i的元素出现的次数,存入数组C的第i项 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加) 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1 当输入的元素是 n 个 0 到 k 之间的整数时,计数排序的时间复杂度为O(N+K

  • Lua中写排序算法实例(选择排序算法) 2013-12-11

    这篇文章主要介绍了Lua中写排序算法实例,本文用一个选择排序算法为例讲解如何在Lua中写一个排序算法,需要的朋友可以参考下 早在12年的时候,学过一个月的lua,当时看的是<programming in lua>,一直没用过,然后就忘了.现在我下定决心重新学习它. 时间久了,对编程的热情也随之消失殆尽,很难找回当初编程的乐趣了.近来一放假就玩英雄联盟,太浪费时间,玩个十来局一天就过去了,浑浑噩噩的,这实在不是我想过的.所以,今天我把它卸载了.如果你也是英雄联盟玩家,希望你不要沉迷其中. 从事游

  • Python实现的几个常用排序算法实例 2014-01-09

    这篇文章主要介绍了Python实现的几个常用排序算法实例例如直接插入排序.直接选择排序.冒泡排序.快速排序等,需要的朋友可以参考下 前段时间为准备百度面试恶补的东西,虽然最后还是被刷了,还是把那几天的"战利品"放点上来,算法一直是自己比较薄弱的地方,以后还要更加努力啊. 下面用Python实现了几个常用的排序,如快速排序,选择排序,以及二路并归排序等等. #encoding=utf-8 import random from copy import copy def directInse

  • 十种JAVA排序算法实例 2014-06-13

    本文件讲了十种JAVA排序方法(冒泡(Bubble)排序--相邻交换 .选择排序--每次最小/大排在相应的位置 .插入排序--将下一个插入已排好的序列中 .壳(Shell)排序--缩小增量 .归并排序 .快速排序 .堆排序 .拓扑排序 .锦标赛排序 .基数排序)的使用,并提供了实例代码可参考 排序算法有很多,所以在特定情景中使用哪一种算法很重要.为了选择合适的算法,可以按照建议的顺序考虑以下标准: (1)执行时间 (2)存储空间 (3)编程工作 对于数据量较小的情形,(1)(2)差别不大,主要考

  • python算法学习之桶排序算法实例(分块排序) 2014-09-22

    本代码介绍了python算法学习中的桶排序算法实例,大家参考使用吧 # -*- coding: utf-8 -*- def insertion_sort(A): """插入排序,作为桶排序的子排序""" n = len(A) if n <= 1: return A B = [] # 结果列表 for a in A: i = len(B) while i > 0 and B[i-1] > a: i = i - 1 B.insert