专栏首页bigsai两分钟真能搞懂桶排序

两分钟真能搞懂桶排序

前言

在数据结构与算法的排序中,我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏,其实这个也没啥复杂的,算法的排序中,我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏,其实这个也没啥复杂的,桶排序是所有排序中最简单的排序之一。 没毛病老铁,就是最简单的之一。并且桶排序和计数排序基数排序有很多相似和渊源之处。

桶排序思想

其实桶排序重要的是它的思想,而不是具体实现,桶排序从字面的意思上看:

  • 桶:若干个桶,说明此类排序将数据放入若干个桶中。
  • 桶:每个桶有容量,桶是有一定容积的容器,所以每个桶中可能有多个元素。
  • 桶:从整体来看,整个排序更希望桶能够更匀称,即既不溢出(太多)又不太少。

但是这些桶跟排序又有什么关系呢? 首先先说下桶排序的思想,百度百科是这么说的

工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。

用通俗易懂的话来理解:

  • 将待排序的序列分到若干个桶中,每个桶内的元素再进行个别排序。
  • 时间复杂度最好可能是线性O(n),桶排序不是基于比较的排序

当然,桶排序是一种用空间换取时间的排序。

既然是排序,那么最终的结果肯定是从小到大的,桶排序借助桶的位置完成一次初步的排序——将待排序元素分别放至各个桶内。

而我们通常根据待排序元素整除的方法将其较为均匀的放至桶中,如8 5 22 15 28 9 45 42 39 19 27 47 12这个待排序序列,假设放入桶编号的规则为:n/10。这样首先各个元素就可以直接通过整除的方法放至对应桶中。而右侧所有桶内数据都比左侧的要大!

在刚刚放入桶中的时候,各个桶的大小相对可以确定,右侧都比左侧大,但桶内还是无序的,对各个桶内分别进行排序,再依次按照桶的顺序、桶内序列顺序得到一个最终排序的序列。

以上就是桶排序在算法上的思想了。如果使用java具体实现的话思路也很简单:用List[]类型的集合数组表示桶,每个List代表一个桶,将数据根据整除得到的值直接放到对应编号的集合里面去,再依次进行排序就可以了。

桶排序算法分析

上面讲了桶排序的具体思想,但是你是不是总觉得心理没那么踏实呢,这就完了?总觉得怪怪的是吧?

桶排序确实有很多不一样的地方,无论是算法时间复杂度还是整个算法的流程,都不如啥快排啦、归并啦这些传统排序来的实在。

时间复杂度分析

桶排序的时间复杂度到底是多少?

我们假设有n个待排序数字。分到m个桶中,如果分配均匀这样平均每个桶有n/m个元素。首先在这里我郑重说明一下桶排序的算法时间复杂度有两部分组成:

  • 1.遍历处理每个元素,O(n)级别的普通遍历
  • 2.每个桶内再次排序的时间复杂度总和

对于第一个部分,我想大家都应该理解最后排好序的取值遍历一趟的O(n);而第二部分咱们可以进行这样的分析:

  • 如果桶内元素分配较为均匀假设每个桶内部使用的排序算法为快速排序,那么每个桶内的时间复杂度为(n/m) log(n/m)。有m个桶,那么时间复杂度为m * (n/m)log(n/m)=n (log n-log m).

所以最终桶排序的时间复杂度为:O(n)+O(n(log n- log m))`=`O(n+n(log n -log m)) 其中m为桶的个数。我们有时也会写成O(n+c),其中c=n*(log n -log m);

在这里如果到达极限情况n=m时。就能确保避免桶内排序,将数值放到桶中不需要再排序达到O(n)的排序效果,当然这种情况属于计数排序,后面再详解计数排序记得再回顾。

桶排序适用情况

桶排序并且像常规排序那样没有限制,桶排序有相当的限制。因为桶的个数和大小都是我们人为设置的。而每个桶又要避免空桶的情况。所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀,又要要求桶的设计兼顾效率和空间。

待排序序列要求均匀?我要不均匀又会怎么样呢? 会这样:

这样其实相当于只用了有效的很少个数桶,而再看桶排序的时间复杂度:O(n+n*(log n -log m))m取向1,log m去向0.整个复杂度变成O(n+nlogn)从级别来看就是O(nlogn),你瞅瞅你瞅瞅,这种情况就跟没用桶一样,就是快排(或其他排序)的时间复杂度。

那,那不能我搞100000个桶嘛? 不可以,真的不可以,如果100000个桶,你看看会造成什么情况:

这才短短不到100个数,你为了一一映射用100000个空间,空间内容浪费不说,你遍历虽然O(n)也是100000次也比100个的O(nlogn)大上很多啊,真是折了夫人又折兵。

所以现在明白前面说的话了吧:数要相对均匀分布,桶的个数也要合理设计。总之桶排序是一种用空间换取时间的排序。在设计桶排序,你需要知道输入数据的上界和下界,看看数据的分布情况,再考虑是否用桶排序,当然如果能用好桶排序,效率还是很高的!

实现一个桶排序

在这里用java给大家实现一个桶排序。假设序列为:1 8 7 44 42 46 38 34 33 17 15 16 27 28 24;我们选用5个桶进行桶排序。

import java.util.ArrayList;
import java.util.List;
//微信公众号:bigsai
public class test3 {
    public static void main(String[] args) {
        int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
        List[] buckets=new ArrayList[5];
        for(int i=0;i<buckets.length;i++)//初始化
        {
            buckets[i]=new ArrayList<Integer>();
        }
        for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中
        {
            int index=a[i]/10;//对应的桶号
            buckets[index].add(a[i]);
        }
        for(int i=0;i<buckets.length;i++)//每个桶内进行排序(使用系统自带快排)
        {
            buckets[i].sort(null);
            for(int j=0;j<buckets[i].size();j++)//顺便打印输出
            {
                System.out.print(buckets[i].get(j)+" ");
            }
        }   
    }
}

打印结果为:

结语

至此,桶排序就讲完了,当然本文可能有地方讲的不好或者拥有纰漏之处还请大佬指出,后面还会讲解计数排序、基数排序并且将三者进行归纳总结!

本文分享自微信公众号 - bigsai(bigsai),作者:bigsai

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一种O(n)的排序——计数排序引发的围观风波

    计算机课上,老师给一串数字6 1 6 9 9 1 4 2 1 5 8 8,问道:这一串数字,你们写个程序给我看,要求效率较高。学不出来的别下课了。

    bigsai
  • 一种非大小排序(先后关系排序)—拓扑排序

    在以前很多人可能听过拓扑排序,但可能认为它太难而不愿接触学习,也不清楚是排啥序的,然而拓扑排序实际很简单,生活中也很常用,面试笔试也会遇到,所以掌握拓扑排序已是...

    bigsai
  • 「干货总结」程序员必知必会的十大排序算法

    身为程序员,十大排序是是所有合格程序员所必备和掌握的,并且热门的算法比如快排、归并排序还可能问的比较细致,对算法性能和复杂度的掌握有要求。bigsai作为一个负...

    bigsai
  • 桶排序/基数排序(Radix Sort)

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要...

    瑾诺学长
  • 10.1 内部排序

    1、排序(Sorting)时计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。

    C语言入门到精通
  • 写代码?程序猿?你不能不懂的八大排序算法的Python实现

    信息获取后通常需要进行处理,处理后的信息其目的是便于人们的应用。信息处理方法有多种,通常由数据的排序,查找,插入,删除等操作。本章介绍几种简单的数据排序算法和高...

    风骨散人Chiam
  • 漫画:“排序算法” 大总结

    如果原始数组本来已经接近有序,只需要较少的比较交换次数即可完成排序。比如下面这个数组,只有7和8是逆序的:

    小灰
  • 排序算法总括-java版

    内部排序就是仅仅依赖于内存就可以进行的排序,比如有交换排序、插入排序、选择排序、归并排序、基数排序

    shengjk1
  • 八大排序算法详解_面试+提升

    八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

    Java帮帮
  • 八大排序算法

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说...

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券