转载

用JAVA实现桶排序（Bucket Sort0)

用JAVA实现桶排序：

<b>import</b> java.util.ArrayList;
<b>import</b> java.util.Arrays;
<b>import</b> java.util.Collections;
<b>import</b> java.util.List;

<font><i>/*
 * Java程序使用基数排序算法对整数数组进行排序。
 * input: [80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 50]
 * output: [0, 10, 20, 30, 40, 50, 50, 60, 70, 80, 90]
 * 
 * 解决方案的时间复杂性:
 *     最佳情况O（n）; 平均情况O（n）; 最坏情况O（n ^ 2）。
 * 
 */</i></font><font>

<b>public</b> <b>class</b> BuckeSort {

  <b>public</b> <b>static</b> <b>void</b> main(String[] args) {

    System.out.println(</font><font>"Bucket sort in Java"</font><font>);
    <b>int</b>[] input = { 80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 50 };

    System.out.println(</font><font>"integer array before sorting"</font><font>);
    System.out.println(Arrays.toString(input));

    </font><font><i>// sorting array using radix Sort Algorithm</i></font><font>
    bucketSort(input);

    System.out.println(</font><font>"integer array after sorting using bucket sort algorithm"</font><font>);
    System.out.println(Arrays.toString(input));

  }

  </font><font><i>/**
   * 
   * @param input
   */</i></font><font>
  <b>public</b> <b>static</b> <b>void</b> bucketSort(<b>int</b>[] input) {
    </font><font><i>// get hash codes</i></font><font>
    <b>final</b> <b>int</b>[] code = hash(input);
    
    </font><font><i>// create and initialize buckets to ArrayList: O(n)</i></font><font>
    List[] buckets = <b>new</b> List[code[1]];
    <b>for</b> (<b>int</b> i = 0; i < code[1]; i++) {
      buckets[i] = <b>new</b> ArrayList();
    }
    
    </font><font><i>// distribute data into buckets: O(n)</i></font><font>
    <b>for</b> (<b>int</b> i : input) {
      buckets[hash(i, code)].add(i);
    }
    
    </font><font><i>// sort each bucket O(n)</i></font><font>
    <b>for</b> (List bucket : buckets) {
      Collections.sort(bucket);
    }
    
    <b>int</b> ndx = 0;
    </font><font><i>// merge the buckets: O(n)</i></font><font>
    <b>for</b> (<b>int</b> b = 0; b < buckets.length; b++) {
      <b>for</b> (<b>int</b> v : buckets[b]) {
        input[ndx++] = v;
      }
    }
  }

  </font><font><i>/**
   * 
   * @param input
   * @return an array containing hash of input
   */</i></font><font>
  <b>private</b> <b>static</b> <b>int</b>[] hash(<b>int</b>[] input) {
    <b>int</b> m = input[0];
    <b>for</b> (<b>int</b> i = 1; i < input.length; i++) {
      <b>if</b> (m < input[i]) {
        m = input[i];
      }
    }
    <b>return</b> <b>new</b> <b>int</b>[] { m, (<b>int</b>) Math.sqrt(input.length) };
  }

  </font><font><i>/**
   * 
   * @param i
   * @param code
   * @return
   */</i></font><font>
  <b>private</b> <b>static</b> <b>int</b> hash(<b>int</b> i, <b>int</b>[] code) {
    <b>return</b> (<b>int</b>) ((<b>double</b>) i / code[0] * (code[1] - 1));
  }

}


Output
Bucket sort in Java
integer array before sorting
<p>[80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 50]
integer array after sorting using bucket sort algorithm
<p>[0, 10, 20, 30, 40, 50, 50, 60, 70, 80, 90]
</font>

桶排序需要记住的重点：

1）Bucket Sort也称为bin sort，因为您创建Bucket或bin来对输入进行排序。

2）Bucket排序仅在输入均匀分布在一个范围内（如硬币、数字1到100等）时才有用。

3）可以使用链表或数组作为存储桶。数据结构的选择会影响插入时间。也可以将哈希表用作存储桶。

4）bucket排序是一种罕见的O（N）排序算法，即bucket排序的时间复杂度是最佳和平均情况下的线性函数，而不是像quicksort或mergesort那样的NLogN。

5）Bucket排序不是一个稳定的排序算法，因为在一个稳定的算法中，如果两个输入相同，它们将按排序顺序保留它们的位置，而在存储桶中，它取决于您对单个存储桶的排序方式。不过，桶排序也可以变得稳定，称为基数排序。

6）您可以通过递归调用bucket排序或使用单独的排序算法（例如插入排序、冒泡排序或快速排序）对单个bucket中的元素进行排序。

7）Bucket排序是原地排序算法吗？不，它不是。整个想法是输入在移动到桶时自行排序。在最糟糕的情况下（顺序值，但不重复），所需的额外空间与原始数组一样大。

8）Bucket排序的最坏情况复杂性，当所有元素最终都在同一个桶中时为O（n ^ 2），因为它必须通过不同的排序算法进行排序。

9）bucket排序的空间复杂度为o（n），因为即使对无重复的顺序值进行排序，也需要一个与原始数组一样大的数组。

原文 https://www.jdon.com/51864

正文到此结束