未加星标

Java排序算法--桶式排序(Bucket Sort)

字体大小 | |
[系统(linux) 所属分类 系统(linux) | 发布者 店小二05 | 时间 20160901 | 作者 红领巾 ] 0人收藏点击收藏

任何只使用比较的一般排序算法的最坏情况下需要运行时间Ω(NlogN),但是记住,在某些特殊情况下以线性时间进行排序仍然是可能的。

一个简单的例子是桶式排序(bucket sort)。为使桶式排序能够正常工作,必须要有一些附加的信息。输入数据A1,A2,A3,…,AN必须只由小于M的正整数组成(显然还可以对其进行扩充)。如果是这种情况,那么算法很简单:使用一个大小为M的称为count的数组,它被初始化为全0。于是,count有M个单元或称桶,这些桶初始化为空。当读Ai时,count[Ai]增1。在所有的输入数据读入后,扫描数组count,打印出排序后的表。该算法用时O(M+N)。如果M为O(N),那么总量就是O(N)。

桶式排序的代码如下:

public class A {
/**
* 输入数据都小于M值,假如M默认值是10
*/
public static final int M = 10;
public static void main(String[] args) {
int[] count = new int[M];
/**
* 假设输入数据是5,4,3,9,8,6,7
*/
Scanner sc = new Scanner(System.in);
System.out.println("请输入小于"+M+"的整数");
while(sc.hasNextInt()){
int i = sc.nextInt();
if(i==0){
break;
}
System.out.println("输入的数据是: "+i);
count[i] = i;
}
System.out.println("排序后count数组中元素:");
printCount(count);
}

/**
* @param count 元素都是正整数的int数组
*/
public static void printCount(int[] count){
for(int i=0;i<count.length;i++){
if(count[i]!=0){
System.out.print(count[i]+" ");
}
}
}

}

运行结果:

请输入小于10的整数
5
输入的数据是: 5
4
输入的数据是: 4
7
输入的数据是: 7
8
输入的数据是: 8
2
输入的数据是: 2
1
输入的数据是: 1
0
排序后count数组中元素:
1 2 4 5 7 8

虽然这个算法似乎打破了下界,但事实上并没有,因为它使用了比简单比较更为强大的操作。通过使适当的桶增值,算法在单位时间内实质上执行了一个M-路比较。这类似于用在可扩散列上的策略。

该算法确实提出了用于证明下界的模型的合理性问题。这个模型实际上是一个强模型,因为通用的排序算法不能对于它可以期望见到的输入类型做假设,而是必须仅仅基于排序信息做一些决策。很自然,如果存在额外的可用信息,我们应该有望找到更为有效的算法,否则这些信息就被浪费了。

尽管桶式排序看似太一般而用处不大,但是实际上却存在许多其输入只是一些小整数的情况,使用像快速排序这样的排序方法真的是小题大作了。

本文地址:http://www.linuxidc.com/Linux/2016-09/135312.htm


Java排序算法--桶式排序(Bucket Sort)

本文系统(linux)相关术语:linux系统 鸟哥的linux私房菜 linux命令大全 linux操作系统

主题: 算法Java数据Linux决策
分页:12
转载请注明
本文标题:Java排序算法--桶式排序(Bucket Sort)
本站链接:http://www.codesec.net/view/483474.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 系统(linux) | 评论(0) | 阅读(21)