`

counting sort

prototypeJ#XHTMLHTML 
阅读更多
counting sort

------
counting sort  概述

输入是 0-k 之间的整数，通过 计算比每个值小的值的个数来排序，

------
性能

不是 comparation sort，

时间复杂度是 O(n)
空间复杂度是 O(n)

------
排序步骤

* 求出 最小、最大 值
* 初始化 计数数组
* 遍历 input 数组，计数
* 由计数数组 求出 大于等于 每个数的个数，
* 遍历 输入数组，根据计数结果每个输入值 排序后的 位置，组成输出数组，
* 输出
*

------
例子

* js (count_sort.js) 
var arr_countsort = [ 78, 13, 6, 177, 26, 90, 288, 45, 62, 83 ];

/**
 * count sort<br />
 * <b>思路：</b><br />
 * 输入是 0-k 之间的整数，通过计算比每个整数小的数的个数从而找到每个数的位置，<br>
 * 不是比较排序，<br />
 * <b>时间复杂度：</b>O(n)<br />
 * <b>空间复杂度：</b>O(n)<br />
 * 
 * @author kuchaguangjie
 * @date 2011年1月2日
 * @return
 */
function CountSort(inputArr) {
	this.inputArr = inputArr;
	this.initMinMax(inputArr);
	this.totalCount = this.inputArr.length; // 总输入个数
	this.rangeCount = this.maxNum - this.minNum + 1; // 数的跨度 = (max - min + 1)
	this.countArr = new Array(this.rangeCount); // 记录每个可取值的 个数 & 比自己小的数的个数
	this.resultArr = []; // 结果数组
}
CountSort.prototype.sort = function() {
	// step 1, init
	for ( var i = 0; i < this.rangeCount; i++) {
		this.countArr[i] = 0;
	}
	// step 2, count
	for ( var j = 0; j < this.totalCount; j++) {
		this.countArr[this.inputArr[j] - this.minNum]++;
	}
	for ( var k = 1; k < this.rangeCount; k++) {
		this.countArr[k] = this.countArr[k] + this.countArr[k - 1];
	}
	// step 3, find position by count,and generate output
	for ( var x = this.totalCount; x >= 1; x--) {
		var v = this.inputArr[x - 1];
		this.resultArr[--this.countArr[v - this.minNum]] = v;
	}
	return this.resultArr;
};
/**
 * 求 最大、最小 值
 * 
 * @param inputArr
 * @return
 */
CountSort.prototype.initMinMax = function(inputArr) {
	if (inputArr.length == 0) {
		return;
	}
	this.minNum = inputArr[0];
	this.maxNum = inputArr[0];
	for ( var i = 0; i < inputArr.length; i++) {
		if (this.minNum > inputArr[i]) {
			this.minNum = inputArr[i];
		} else if (this.maxNum < inputArr[i]) {
			this.maxNum = inputArr[i];
		}
	}
};


* html 
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<script type="text/javascript" src="js/count_sort.js"></script>
</head>
<body>
<input type="button" value="counting sort" onclick="alert(new CountSort(arr_countsort).sort());" />
</body>
</html>


*

------
分享到：
| quick sort
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    AlgorithmMan by Iori（Counting Sort）

    CountingSort为AlgorithmMan中的计数排序演示工具（这是可执行文件；需要.net 4.0支持；非源代码）。 原文：C#算法设计排序篇之08-计数排序（附带动画演示程序） 链接：...

    排序算法-基于C语言实现的排序算法之CountingSort实现.zip

    **C语言实现CountingSort：** C语言的简洁和高效使得它成为实现算法的理想选择。以下是一个简单的Counting Sort C语言实现的框架： ```c #include void countingSort(int arr[], int n) { // 步骤1和2：初始化...

    计数排序JAVA实现counting sort algorithm

    public static int[] countingSort(int[] arr) { // Step 1: 获取数组最大值 int max = Arrays.stream(arr).max().getAsInt(); // Step 2: 初始化计数数组 int[] countArray = new int[max + 1]; // Step ...

    排序算法之CountingSort

    python 排序算法之CountingSort

    基数排序_Countingsort.zip

    基数排序_Countingsort

    CountingSort:计数排序算法的实现

    var countingSort = require ( './countingSort.js' ) ; // Construct input [0, 5], therefore an array of size 6 is needed // for the temporary storage space. var input = [ 2 , 5 , 3 , 0 , 2 , 3 , 0 , 3 ...

    countingSort：计数排序是一种基于特定范围内的键的排序技术。 它通过计算具有不同键值（有点像哈希）的对象数来工作

    function countingSort(arr) { const min = Math.min(...arr); const max = Math.max(...arr); const count = new Array(max - min + 1).fill(0); arr.forEach(num =&gt; count[num - min]++); const sortedArr...

    radix sort

    在这个例子中，`countingSort`函数实现了计数排序，`radixsort`函数负责调用`countingSort`并处理从低位到高位的每一位。这段代码适用于整数数组的排序，如果需要处理浮点数或者负数，还需要进行适当的修改。 总结...

    python 实现 排序 课程设计 代码

    计数排序（Counting Sort） 循环排序（Cycle Sort） 双重排序（Double Sort） 荷兰国旗排序（Dutch National Flag Sort） 交换排序（Exchange Sort） 外部排序（External Sort） 侏儒排序（Gnome Sort） 堆排序...

    matlab开发-sort1m

    7. **计数排序（Counting Sort）、桶排序（Bucket Sort）、基数排序（Radix Sort）**：这些是针对特定类型数据（如非负整数）的排序算法，可以在一定条件下达到线性时间复杂度。 "sort1.m"的实现可能考虑了算法效率...

    count_sort.zip_count_sort_in

    在`main`函数中，我们创建了一个测试数组并调用`countingSort`函数进行排序，最后打印出排序后的结果。 需要注意的是，计数排序不是稳定的排序算法，即相等的元素可能会改变它们原来的相对顺序。此外，当元素范围很...

    sort.cpp_排序算法演示程序_

    7. **计数排序（Counting Sort）**：非基于比较的排序算法，适用于整数排序，尤其在数据范围不大的情况下效率极高。 在"sort.cpp"中，每种排序算法的实现都可能包含关键步骤的注释，这对于初学者理解各种排序算法的...

    经典算法的C#源码实现

    经典的排序算法C#源码，包括： 经典排序算法 - 快速排序Quick sort 经典排序算法 - 桶排序Bucket sort 经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序...经典排序算法 - 计数排序Counting sort

    CSort内排序算法

    7. **计数排序（Counting Sort）**： 计数排序是一种非基于比较的排序算法，适用于待排序的元素范围不大的情况。它通过统计每个元素出现的次数，然后计算出每个元素应该在输出序列中的位置。其时间复杂度为O(n+k)，...

    常用的8个Python排序算法

    1. 冒泡排序（Bubble Sort） def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] &gt; arr[j+1]: ...8. 计数排序（Counting Sort） 解压密码 douge

    java实现计数排序算法

    countingSort 方法实现了计数排序算法。首先，我们遍历一遍原数组，找出其中的最大值，以确定计数数组的大小。然后，创建计数数组 count，并将每个元素的出现次数记录在计数数组中。接下来，根据计数数组中的元素...

    常用的十种java排序算法实现

    1. 冒泡排序（Bubble Sort） public static void bubbleSort(int...7. 计数排序（Counting Sort） 8. 桶排序（Bucket Sort） 9. 基数排序（Radix Sort） 10. 希尔排序（Shell Sort） 解压密码 douge

    Sort源代码

    7. 计数排序（Counting Sort）：非基于比较的排序算法，适用于整数排序，通过统计每个元素出现的次数，直接确定每个元素的位置。 8. 桶排序（Bucket Sort）：当输入数据服从均匀分布时，桶排序非常有效。将数据分配...

    排序算法大全

    Rank Sort是Comparison Counting Sort的变形，省略了资料排名阵列，而在每一次需要时再去扫瞄资料算出，因此速度更慢。然而，这个程式并没有考虑到键值相同的情况，因此并不实用。 Distribution Counting Sort也是 ...

    算法编程题 排序、搜索、图论、动态规划

    计数排序（Counting Sort） 桶排序（Bucket Sort） 基数排序（Radix Sort） 搜索算法 线性搜索（Linear Search） 二分搜索（Binary Search） 深度优先搜索（Depth-First Search） 广度优先搜索（Breadth-First ...

Magicbox
Global site tag (gtag.js) - Google Analytics