九、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

9.1 算法描述

设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。

九、桶排序（Bucket Sort）

package bucketsort;

//桶排序：将N个数，分成m个桶，桶之间的元素递增，然后对桶内的元素进行排序，最后输出所有元素
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * @author Gavenyeah
 * @date Time: 2016年4月20日下午10:12:43
 * @des:
 */
public class BucketSort {
    int bucketSize = 10;
    int arraySize = 10000;

    public static void main(String[] args) {
        BucketSort bs = new BucketSort();
        int[] array = bs.getArray();
        bs.bucketSort(array);
    }

    public int[] getArray() {
        int[] arr = new int[arraySize / 3];
        Random r = new Random();
        for (int i = 0; i < arraySize; i++) {
            arr[i] = r.nextInt(100000);
        }
        return arr;
    }

    public void bucketSort(int[] a) {
        @SuppressWarnings("unchecked")
        List<Integer> bucket[] = new ArrayList[bucketSize];
        for (int i = 0; i < a.length; i++) {
            int temp = a[i] / 10000;
            if (bucket[temp] == null) {
                bucket[temp] = new ArrayList<Integer>();
            }
            bucket[temp].add(a[i]);
        }
        // 对各个桶内的list中的元素进行排序
        for (int j = 0; j < bucketSize; j++) {
            insertSort(bucket[j]);// 对桶内的元素进行排序
            printList(bucket[j]);// 输出桶中的元素
        }
    }

    public void printList(List<Integer> list) {
        while (list.size() > 0) {
            System.out.print(list.remove(0) + "\t");
        }
    }

    public void insertSort(List<Integer> list) {// 对每个list进行排序
        Collections.sort(list);
    }
}

九、桶排序（Bucket Sort）

九、桶排序（Bucket Sort）

相关推荐