【算法导论学习-014】计数排序(CountingSortTest)

参考:《算法导论》P194页 8.2节 Counting sort

1、Counting sort的条件

待排序数全部分布在0~k之间,且k是已知数;或者分布在min~max之间,等价于分布在0~max-min之间,max和min是已知数。

2、java 实现

/**
 * 创建时间:2014年8月17日 下午3:22:14 项目名称:Test
 *
 * @author Cao Yanfeng
 * @since JDK 1.6.0_21 类说明: 计数排序法,复杂度O(n), 条件:所有数分布在0~k,k为已知数
 */
public class CountingSortTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int[] array = { 7, 2, 5, 9, 1, 2, 7, 3, 0, 3, 4, 7, 8, 6, 6, 2, 0, 0,
				7, 10, 11 };// 0~11之间的整数
		int[] result = countingSort(array, 11);
		for (int i : result) {
			System.out.println(i);
		}

	}

	/* 计数排序,注意java数组下标从0开始,所以temp的长度为k+1, */
	public static int[] countingSort(int[] array, int k) {
		int[] temp = new int[k + 1];
		int[] result = new int[array.length];
		for (int i = 0; i < k; i++) {
			temp[i] = 0;
		}

		for (int i = 0; i < array.length; i++) {
			temp[array[i]] = temp[array[i]] + 1;
		}
		for (int i = 1; i < temp.length; i++) {
			temp[i] += temp[i - 1];

		}
		/* temp[array[i]]为所有数字的计数,即数组长度,注意下标为temp[array[i]]-1 */
		for (int i =<span style="font-family: Arial, Helvetica, sans-serif;">array.length-1</span>; i >=0; i--) {
			/*
			 * 关键点:不大于array[i]的元素有temp[array[i]]个,则array[i]的排序位置是temp[array[i]]-1
			 */
			result[temp[array[i]] - 1] = array[i];
			temp[array[i]] = temp[array[i]] - 1;
		}
		return result;
	}

}

****************************************************************************************************************************************************************************************

对于未知数组,其实可以用O(n)的复杂度先探测到min和max,即k=max-min,数组每个元素都减去min,对新数组进行计数排序,排序后新数组再加上min即可。总的复杂度仍然为O(n)。

【算法导论学习-014】计数排序(CountingSortTest)

时间: 08-14

【算法导论学习-014】计数排序(CountingSortTest)的相关文章

[一周一算法]算法导论学习之计数排序

计数排序是一种线性时间的排序,同时也是一种非比较排序 代码如下: 1 void CountingSort(int *data, int k, int num) // A ~ data[], B ~ aimArray[], C ~ tempArray[] 2 { 3 int *aimArray = new int[num]; 4 int *tempArray = new int[k + 1]; 5 for (int i = 0; i <= k; i++) 6 tempArray[i] = 0; 7

【算法导论学习-015】基数排序(Radix sort)

1.<算法导论>P197页 8.3节Radix sort 2.java实现 这里仅仅对[算法导论学习-014]计数排序 的参数进行了修改,同时仅仅修改了一行代码. /** * 创建时间:2014年8月17日 下午4:05:48 * 项目名称:Test * @author Cao Yanfeng * @since JDK 1.6.0_21 * 类说明: 利用计数排序实现基数排序 * 条件:待排序的所有数位数相同,注意,即便不相同,也可以认为是最多那个位数,如下面的例子可以认为都是3位数 */ p

排序算法的c++实现——计数排序

任何比较排序算法的时间复杂度的上限为O(NlogN), 不存在比o(nlgN)更少的比较排序算法.如果想要在时间复杂度上超过O(NlogN)的时间复杂度,肯定需要加入其它条件.计数排序就加入了限制条件,从而使时间复杂度为O(N). 计数排序的核心思想(来自算法导论):计数排序要求待排序的n个元素的大小在[0, k]之间,并且k与n在一个数量级上,即k=O(n).对于每一个输入元素x, 确定小于等于x的个数为i.利用这一信息,就可以把元素x放到输出数组的正确位置,即把元素x放到输出数组下标为i-1

【算法导论-学习笔记】以线性时间增长的排序——计数排序

计数排序是一种能够达到运行时间能够线性时间θ(n)的排序算法.在排序算法里算是最快的算法之一,当然,他有很强烈的前提.下面开始介绍一下技术排序(Counting Sort). 算法思想 计数排序假设n个输入元素中的每一个都是介于0到k之间的整数,此处k为某个整数.这样可以用一个数组C[0..k]来记录待排序数组里元素的数量.当k=O(n)时,计数排序的运行时间为θ(n). 注:关于C[0..k],用键值对描述的话,待排序元素是键,相同元素的个数是值.例:待排序数组<2,3 , 6,4 , 1 ,

算法导论 学习资源

学习的过程会遇到些问题,发现了一些比较好的资源,每章都会看下别人写的总结,自己太懒了,先记录下别人写的吧,呵呵. 1  Tanky Woo的,每次差不多都看他的 <算法导论>学习总结 - 1.前言 <算法导论>学习总结 - 2.第一章 && 第二章 && 第三章 <算法导论>学习总结 - 3.第四章 && 第五章 <算法导论>学习总结 - 4.第六章(1) 堆排序 <算法导论>学习总结 - 5.第六

【算法导论学习-016】两个已排过序的等长数组的中位数(median of two sorted arrays)

问题来源 <算法导论>P223 9.3-8: Let X[1..n] and Y[1..n] be two arrays, each containing nnumbers already in sorted order. Give an O(lgn)-time algorithm to find themedian of all 2n elements in arrays X and Y. 翻译过来即:求两个等长(n个元素)的已排序数组A和B的中位数 方案1:对两个数组进行归并直到统计到第n

算法导论学习---红黑树具体解释之插入(C语言实现)

前面我们学习二叉搜索树的时候发如今一些情况下其高度不是非常均匀,甚至有时候会退化成一条长链,所以我们引用一些"平衡"的二叉搜索树.红黑树就是一种"平衡"的二叉搜索树,它通过在每一个结点附加颜色位和路径上的一些约束条件能够保证在最坏的情况下基本动态集合操作的时间复杂度为O(nlgn).以下会总结红黑树的性质,然后分析红黑树的插入操作,并给出一份完整代码. 先给出红黑树的结点定义: #define RED 1 #define BLACK 0 ///红黑树结点定义,与普通

【算法导论学习-015】数组中选择第i小元素(Selection in expected linear time)

1.算法思想 问题描述:从数组array中找出第i小的元素(要求array中没有重复元素的情况),这是个经典的"线性时间选择(Selection in expected linear time)"问题. 思路:算法导论215页9.2 Selection in expect linear time 2.java实现 思路:算法导论216页伪代码 /*期望为线性时间的选择算法,输入要求,array中没有重复的元素*/ public static int randomizedSelect(i

算法导论学习---红黑树详解之插入(C语言实现)

前面我们学习二叉搜索树的时候发现在一些情况下其高度不是很均匀,甚至有时候会退化成一条长链,所以我们引用一些"平衡"的二叉搜索树.红黑树就是一种"平衡"的二叉搜索树,它通过在每个结点附加颜色位和路径上的一些约束条件可以保证在最坏的情况下基本动态集合操作的时间复杂度为O(nlgn).下面会总结红黑树的性质,然后分析红黑树的插入操作,并给出一份完整代码. 先给出红黑树的结点定义: #define RED 1 #define BLACK 0 ///红黑树结点定义,与普通的二