Java排序算法--桶式排序（Bucket Sort）

任何只使用比较的一般排序算法的最坏情况下需要运行时间Ω（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