分桶排序

  桶排序采用了分而治之的思想。在处理大量数据的排序时，如果收到内存和时间的限制时，我们将数据进行拆分到小单元，单元内进行排序，这样就可以使用小内存排序大数据。也可以使用多线程排序小单元数据，最后进行数据合并完成整个数据的排序。

在桶排序中关键点是数据分桶的处理。如果需要排序的数据不是线性递增的，就可能导致分桶数据不均匀，极端情况出现数据全部分到一个桶中，编程单个算法排序了。桶排序适合均匀分布的相对比较密集的数据。

代码demo实现

import java.util.ArrayList;
import java.util.List;
/** * @author zhw * @description * @date 2021-04-13 19:27 */
public class BucketSort {
   
	//设置桶内数据大小
    private static final int BUCKET_SIZE = 10;

    public Integer[] bucketSort(Integer[] arr){
   
    	//桶数量
        int bucketNumber = arr.length % BUCKET_SIZE == 0 ? arr.length / BUCKET_SIZE : arr.length / BUCKET_SIZE + 1;
        //桶创建
        Bucket[] buckets = new Bucket[bucketNumber];
        for (int i = 0;i<buckets.length;i++){
   
            buckets[i] = new Bucket();
        }
        //数据分桶
        for(int i = 0;i<arr.length;i++){
   
            int index = arr[i] / bucketNumber;
            //将空间一致的数据分到同一个桶中
            Bucket bucket = buckets[index>bucketNumber?bucketNumber-1:index];
            bucket.add(arr[i]);
        }
        //开始排序
        int index = 0;
        for(int i = 0;i<buckets.length;i++){
   
            Integer[] sort = buckets[i].sort();
            //数据合并
            for(int j = 0;j<sort.length;j++){
   
                arr[index++] = sort[j];
            }
        }
        return arr;
    }
    private class Bucket{
   
    	//桶内计数
        private int num = 0;
        List<Integer> data = new ArrayList<>();
        public Bucket add(Integer d){
   
            num++;
            data.add(d);
            return this;
        }
        public Integer[] sort(){
   
            Integer[] integers = data.toArray(new Integer[data.size()]);
            quickSort(integers);
            return integers;
        }
		//桶内使用快排
        private void quickSort(Integer[] arr){
   
            qsort(arr, 0, arr.length-1);
        }
        private void qsort(Integer[] arr, int low, int high){
   
            if (low < high){
   
                int pivot=partition(arr, low, high);        //将数组分为两部分
                qsort(arr, low, pivot-1);                   //递归排序左子数组
                qsort(arr, pivot+1, high);                  //递归排序右子数组
            }
        }
        private int partition(Integer[] arr, int low, int high){
   
            int pivot = arr[low];     //枢轴记录
            while (low<high){
   
                while (low<high && arr[high]>=pivot) --high;
                arr[low]=arr[high];             //交换比枢轴小的记录到左端
                while (low<high && arr[low]<=pivot) ++low;
                arr[high] = arr[low];           //交换比枢轴小的记录到右端
            }
            //扫描完成，枢轴到位
            arr[low] = pivot;
            //返回的是枢轴的位置
            return low;
        }

    }
}

测试

public class Test {
   
    public static void main(String[] args) {
   
        BucketSort bucketSort = new BucketSort();
        Integer[] a = {
   2,3,4,5,676,74,23,4,5,6,1,23,4,5,323,542,35,435,234,53,1324,345,3453,1234};
        Integer[] integers = bucketSort.bucketSort(a);
        System.out.println(Arrays.asList(integers).toString());
    }
}

从10亿数据中找出中位数？

假设这10亿数据都是无符号整数。我们可以创建2^16个桶。我们取数据中的高16位进行分桶，分桶方式如下：

每个桶都记录桶中数据数量num，然后将各个桶的num相加，得到中位数落到哪个桶内，然后将桶内数据进行排序后得到中位数。