十大排序——9.桶排序

这篇文章我们来介绍一下桶排序

1.介绍

2.代码实现

3.总结与思考

1.介绍

桶排序和计数排序一样，都不是基于比较进行排序的。

下面通过一个例子来理解一下桶排序吧。

首先，给你一个无序数组[ 20,18,28,66,25,31,67,30 ]，然后，我们对其进行一个划分，比如十位数为1的放一起排，十位数为2的放一起排等等。结果就是我创造了10个桶，每个桶里面都放着十位数相同的那些数，然后，我在这些桶里再实现这些数据的有序性，然后，我再依次将这些数据取出来，这样就保证了数据的有序性。

下面看一下介绍：

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（O(n)）。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。

基本思想

桶排序的思想近乎彻底的分治思想。

桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。

然后基于某种映射函数 f ，将待排序列的关键字 k 映射到第 i 个桶中 (即桶数组 B 的下标 i ) ，那么该关键字 k 就作为 B[ i ] 中的元素 (每个桶B[ i ] 都是一组大小为 N/M 的序列 )。

接着将各个桶中的数据有序的合并起来 : 对每个桶B[ i ] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[ 0 ] …. B[ M ] 中的全部内容即是一个有序序列。

补充： 映射函数一般是 f = array[ i ] / k; k^2 = n；n 是所有元素个数

为了使桶排序更加高效，我们需要做到这两点：

1、在额外空间充足的情况下，尽量增大桶的数量；
2、使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中；

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

实现逻辑

设置一个定量的数组当作空桶子。
寻访序列，并且把项目一个一个放到对应的桶子去。
对每个不是空的桶子进行排序。
从不是空的桶子里把项目再放回原来的序列中。

2.代码实现

下面看一下代码实现：

package Sorts;

import java.util.*;

//桶排
public class RadixSort {
    public static void main(String[] args) {
        int [] arr = new int[]{193,255,12,6,78,50,31,564};
        bucketSort(arr);;
        System.out.println(Arrays.toString(arr));

    }

    public static void bucketSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        // 建立桶，个数和待排序数组长度一样
        int length = array.length;

        LinkedList<Integer>[] bucket = (LinkedList<Integer>[]) new LinkedList[length];

        // 待排序数组中的最大值
        int maxValue = Arrays.stream(array).max().getAsInt();
        // 根据每个元素的值，分配到对应范围的桶中
        for (int i = 0; i < array.length; i++) {
            int index = toBucketIndex(array[i], maxValue, length);
            // 没有桶才建立桶(延时)
            if (bucket[index] == null) {
                bucket[index] = new LinkedList<>();
            }
            // 有桶直接使用
            bucket[index].add(array[i]);
        }

        // 对每个非空的桶排序，排序后顺便存入临时的List，则list中已经有序）
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
                temp.addAll(bucket[i]);
            }
        }

        // 将temp中的数据写入原数组
        for (int i = 0; i < length; i++) {
            array[i] = temp.get(i);
        }
    }

    private static int toBucketIndex(int value, int maxValue, int length) {
        return (value * length) / (maxValue + 1);
    }
    
    /**
     *
    public static void sort(int arr[] ){
        //定义二维数组
        int [][] bucket = new int[10][arr.length];
        //定义记录桶中数据个数的数组
        int [] bucketElement = new int[10];

        for (int i = 0; i <arr.length ; i++) {
            int element = arr[i] % 10;
            bucket[element][bucketElement[element]] = arr[i];
            bucketElement[element]++;
        }

        int index = 0;

        for (int k = 0; k <bucketElement.length ; k++) {
            if (bucketElement[k]!=0){
                for (int l = 0; l <bucketElement [k] ; l++) {
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            bucketElement[k]=0;
        }
    }
     */
}

注释的部分可能更好理解一点