用JAVA实现桶排序（Bucket Sort0)

<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>