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

本文主要是介绍Java排序算法--桶式排序（Bucket Sort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

  一个简单的例子是桶式排序（bucket sort）。为使桶式排序能够正常工作，必须要有一些附加的信息。输入数据A₁，A₂，A₃，…，A_N必须只由小于M的正整数组成（显然还可以对其进行扩充）。如果是这种情况，那么算法很简单：使用一个大小为M的称为count的数组，它被初始化为全0。于是，count有M个单元或称桶，这些桶初始化为空。当读A_i时，count[A_i]增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.hasNextI

这篇关于Java排序算法--桶式排序（Bucket Sort）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---