桶排序 订阅
桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。 展开全文
桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
信息
领    域
计算机算法
要    求
数据的长度必须完全一样
公    式
Data=rand()/10000+10000
原    理
桶排序利用函数的映射关系
中文名
桶排序
性    质
平均情况下桶排序以线性时间运行
数据结构设计
链表可以采用很多种方式实现
桶排序定义
假定:输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间(桶),每桶大小1/n:[0, 1/n), [1/n, 2/n), [2/n, 3/n),…,[k/n, (k+1)/n ),…将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组,指向桶(链表)。
收起全文
精华内容
参与话题
问答
  • 桶排序

    千次阅读 2020-05-08 14:36:06
    桶排序 package com.mtons.mblog.leetcode; import java.util.Arrays; import java.util.LinkedList; /** * 桶排序假设输入元素均匀而独立的分布在区间[0,1)上; * 桶排序的核心思想是,将[0,1)分为n个大小...

    桶排序

    package com.mtons.mblog.leetcode;
    
    import java.util.Arrays;
    import java.util.LinkedList;
    
    /**
     * 桶排序假设输入元素均匀而独立的分布在区间[0,1)上;
     * 桶排序的核心思想是,将[0,1)分为n个大小相同的子区间,
     * 上一个区间里的元素都比下一个区间里的元素小,然后对
     * 所有区间里的元素排序,最后顺序输出所有区间里的元素,
     * 达到对所有元素排序的目的。
     *桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:
     *
     * 在额外空间充足的情况下,尽量增大桶的数量
     * 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
     * 同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
     *
     */
    public class BucketSort {
        public void sort(Double[] a) {
            int n = a.length;
    
            /**
             * 创建链表(桶)集合并初始化,集合中的链表用于存放相应的元素
             */
            int bucketNum = 10; // 桶数
            LinkedList<LinkedList<Double>> buckets = new LinkedList<LinkedList<Double>>();
            for(int i = 0; i < bucketNum; i++){
                LinkedList<Double> bucket = new LinkedList<Double>();
                buckets.add(bucket);
            }
            // 把元素放进相应的桶中
            for(int i = 0; i < n; i++){
                int index = (int) (a[i] * bucketNum);
                buckets.get(index).add(a[i]);
            }
            // 对每个桶中的元素排序,并放进a中
            int index = 0;
            for (LinkedList<Double> linkedList : buckets) {
                int size = linkedList.size();
                if (size == 0) {
                    continue;
                }
                /**
                 * 把LinkedList<Double>转化为Double[]的原因是,之前已经实现了
                 * 对数组进行排序的算法
                 */
                Double[] temp = new Double[size];
                for (int i = 0; i < temp.length; i++) {
                    temp[i] = linkedList.get(i);
                }
                // 利用插入排序对temp排序
                Arrays.sort(temp);
                for (int i = 0; i < temp.length; i++) {
                    a[index] = temp[i];
                    index++;
                }
            }
    
        }
    
        public static void main(String[] args) {
            Double[] a = new Double[]{0.3, 0.6, 0.5};
            new BucketSort().sort(a);
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
        }
    }
    
    
    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 9,435
精华内容 3,774
关键字:

桶排序