`

counting sort

阅读更多
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>


*

------
分享到:
评论

相关推荐

    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 ...

Global site tag (gtag.js) - Google Analytics