用JAVA实现桶排序(Bucket Sort)

19-03-07 jdon
         

用JAVA实现桶排序:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/*
 * 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)。
 * 
 */

public class BuckeSort {

  public static void main(String args) {

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

    System.out.println("integer array before sorting");
    System.out.println(Arrays.toString(input));

    // sorting array using radix Sort Algorithm
    bucketSort(input);

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

  }

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

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

  /**
   * 
   * @param i
   * @param code
   * @return
   */
  private static int hash(int i, int code) {
    return (int) ((double) 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]

桶排序 需要记住的重点:

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),因为即使对无重复的顺序值进行排序,也需要一个与原始数组一样大的数组。