思想:
设置数组b、c,c用于放置a数组中每个元素的值出现的次数,然后得出a中元素<=i的元素个数再次放入c中,其中c的下标对应于a中每个元素的值.此时c[a[i]-1]就是a[i]在b中的位置.
这种排序适用于待排序的数组元素最大值已经给定的情况下使用,而且待排序的每个元素都>=0。计数排序是一种线性时间复杂度的排序,设定a[0:N-1]中元素的最大值为M,这排序的时间复杂度O(M+N)。
/**
* CountingSort.java
* 计数排序
* @author Administrator
*/
public class CountingSort {
/**
* 无序数组a的元素满足必须有一个最大值为m(m>=0)最小值不小于0
*/
public static void countingSort(int[] a, int m) {
int n = a.length;
int[] b = new int[n];
int[] c = new int[m + 1];
/*
//对c语言是必须的
for(int i = 0; i <=m; i ++)
c[i] = 0;
*/
//存放a中元素等于i的元素个数.
for(int i = 0; i < n; i ++)
c[a[i]] += 1;
//存放a中元素<=i的元素个数.
for(int i=1; i <= m; i ++)
c[i] += c[i-1];
//把a中每个元素放入b中正确的位置.
for(int i = n; i >0; i --)
{
b[c[a[i - 1]] - 1] = a[i - 1];
c[a[i - 1]] -= 1;//a中如果有元素的值相等此句是必须的.
}
//把b[0:n-1]的元素复制到a中
Util.copy(a, b, 0, n-1);
}
public static void main(String[] args) throws Exception {
if (args.length == 0) {
System.out.println("请输入数字(>=0)以空格隔开");
System.exit(-1);
}
int[] a = new int[args.length];
for (int i = 0; i < args.length; i++)
a[i] = Integer.parseInt(args[i]);
//检查输入元素的值.
for(int i=0; i< a.length; i++)
if(a[i]<0){System.out.println("每个元素的值不小于0");System.exit(-
1);}
//获取输入元素的最大值对应的下标.
int mid = 0;
for(int i = 0 ; i < a.length-1; i++){
if(a[mid] < a[i+1]) mid = i+1;
}
countingSort(a, a[mid]);
// 输出排序后的数组元素。
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}
}
分享到:
相关推荐
//排序类 提供int排序的静态方法 有以下排序: 快速排序 堆排序 计数排序 桶排序 归并排序
Java实现计数排序不是C,Java实现计数排序不是C,Java实现计数排序不是C
主要是对算法导论中计数排序的实现
排序算法之计数排序,计数排序是一种线性的排序算法,比基于比较的排序算法效率高,但其应用有特定的领域。我给出了两种策略的计数排序算法,欢迎下载~~如程序中有Bug,恳请指正!
蓝桥杯VIP题和题解
计数排序(代码片段)
本文实例讲述了JS实现的计数排序与基数排序算法。分享给大家供大家参考,具体如下: 计数排序 计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在...
利用python,JavaScript,java,go,PHP等实现: 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆排序 计数排序 桶排序 基数排序
超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称...
算法导论上计数排序算法的vc.60Test实例
计数排序 用C++实现 简单易懂 欢迎下载
C语言版的排序方法---计数排序.非常有用的代码,可以实际中使用。
这些代码是对算法导论上对排序部分的总结,实现了以下排序方法:插入排序,合并排序,堆排序,快速排序,计数排序,每种实现都有详细的注释和相应的测试程序,可查找http://blog.csdn.net/china8848<br>中对相关问题...
几种排序算法的代码实现。c语言版的。排序算法 希尔排序 快速排序 堆排序 归并排序 计数排序
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
以前看过网上的一篇关于一种号称时间复杂度能达到O(n)的不用比较就可以实现排序的算法——计数排序法,这是自己用C写的一个实现,大家可以参考下,欢迎指证。
关于c#的一些算法 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序。。。
计数排序的代码实现,对应分析在我的博客里找,学习和开发的随便下
计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数...
据传为经典排序算法。 选择排序 冒泡排序 快速排序 插入排序 希尔排序 归并排序 基数排序 计数排序 小根堆排序