• 60090

    文章

  • 611

    评论

  • 59

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

桶排序

撸了今年阿里、腾讯和美团的面试,我有一个重要发现.......>>
    private static double[] bucketSort(double[] array){
        //1.得到数列的最大值和最小值,并算出差值d
        double max=array[0];
        double min=array[0];
//        找出最大和最小值
        for (int i = 1; i < array.length; i++) {
            if(array[i] > max){
                max=array[i];
            }
            if(array[i] < min){
                min=array[i];
            }
        }
//        数组的数值范围
        double d=max-min;
        int bucketNum=array.length;//有多少个数值就有多少个桶
//        通的数组
        List<LinkedList<Double>> bucketList=new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new LinkedList<>());
        }
//        将每个数组元素放入桶中,
        for (int i = 0; i < array.length; i++) {
            int num= (int) ((array[i]-min) * (bucketNum-1)/d);
            bucketList.get(num).add(array[i]);
        }
//        对每个桶进行内部排序
        for (int i = 0; i < bucketList.size(); i++) {
            Collections.sort(bucketList.get(i));
        }
//        排好序的数组
        double[] sortArray=new double[array.length];
        int index=0;
        for (LinkedList<Double> list : bucketList) {
            for (Double element : list) {
                sortArray[index++]=element;
            }
        }
         return sortArray;

    }

    public static void main(String[] args) {
        double[] array = { 8.122,0.0023, 10.09, 3.0, 4.12, 2.123, 4.12, 6.421};
        double [] sortedArray = bucketSort(array);
        System.out.println(Arrays.toString(sortedArray));
    }

假设原始数列有n个元素,分成m个桶(我们采用的分桶方式 m=n),平均每个桶的元素个数为n/m。

下面我们来逐步分析算法复杂度:

 

第一步求数列最大最小值,运算量为n。

第二步创建空桶,运算量为m。

第三步遍历原始数列,运算量为n。

第四步在每个桶内部做排序,由于使用了O(nlogn)的排序算法,所以运算量为 n/m * log(n/m ) * m。

第五步输出排序数列,运算量为n。

 

加起来,总的运算量为 3n+m+ n/m * log(n/m ) * m = 3n+m+n(logn-logm) 。

去掉系数,时间复杂度为:

O(n+m+n(logn-logm)) 

 

至于空间复杂度就很明显了:

空桶占用的空间 + 数列在桶中占用的空间 = O(m+n)

桶排序存在如下缺点

如果桶内元素分布极不均衡,极端情况下第一个桶中有n-1个元素,最后一个桶中有1个元素,此时的时间复杂度将退化成O(nlogn)还白白创建了许多空桶

在这种情况下,个人建议用归并或快排代替


 转载至链接:https://my.oschina.net/u/3574106/blog/3062571。

695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

欢迎来到梁钟霖个人博客网站。本个人博客网站提供最新的站长新闻,各种互联网资讯。 还提供个人博客模板,最新最全的java教程,java面试题。在此我将尽我最大所能将此个人博客网站做的最好! 谢谢大家,愿大家一起进步!

转载原创文章请注明出处,转载至: 梁钟霖个人博客www.liangzl.com

0条评论

Loading...


发表评论

电子邮件地址不会被公开。 必填项已用*标注

自定义皮肤
注册梁钟霖个人博客