数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

13 | 线性排序:如何根据年龄给100万用户数据排序?

王争 2018-10-19
上两节中,我带你着重分析了几种常用排序算法的原理、时间复杂度、空间复杂度、稳定性等。今天,我会讲三种时间复杂度是 O(n) 的排序算法:桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的,所以我们把这类排序算法叫作线性排序(Linear sort)。之所以能做到线性的时间复杂度,主要原因是,这三个算法是非基于比较的排序算法,都不涉及元素之间的比较操作。
这几种排序算法理解起来都不难,时间、空间复杂度分析起来也很简单,但是对要排序的数据要求很苛刻,所以我们今天学习重点的是掌握这些排序算法的适用场景
按照惯例,我先给你出一道思考题:如何根据年龄给 100 万用户排序? 你可能会说,我用上一节课讲的归并、快排就可以搞定啊!是的,它们也可以完成功能,但是时间复杂度最低也是 O(nlogn)。有没有更快的排序方法呢?让我们一起进入今天的内容!

桶排序(Bucket sort)

首先,我们来看桶排序。桶排序,顾名思义,会用到“桶”,核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。
桶排序的时间复杂度为什么是 O(n) 呢?我们一块儿来分析一下。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(286)

  • wucj 置顶
    用两个指针a、b:a指针从头开始往后遍历,遇到大写字母就停下,b从后往前遍历,遇到小写字母就停下,交换a、b指针对应的元素;重复如上过程,直到a、b指针相交。
    对于小写字母放前面,数字放中间,大写字母放后面,可以先将数据分为小写字母和非小写字母两大类,进行如上交换后再在非小写字母区间内分为数字和大写字母做同样处理
    2018-10-19
    8
    409
  • 伟忠
    课后思考,利用桶排序思想,弄小写,大写,数字三个桶,遍历一遍,都放进去,然后再从桶中取出来就行了。相当于遍历了两遍,复杂度O(n)
    2018-10-19
    10
    351
  • 渐渐有些掉队的趋势
    2018-10-19
    3
    251
  • 传说中的成大大
    排序算法基本上算是学完了,昨天我在实践快排的时候 我就发现这样一个问题,虽然理解了原理 但是写起来还不是很顺畅,如果写出来的代码跟老师的一模一样 那就不叫理解了原理 那叫背代码,我昨天也去翻了大话数据结构里面的快排 发现代码又不一样,所以我觉得接下来的时间就应该根据思路多实现一下这些排序代码,不能死记硬背代码,多理解原理
    2018-10-19
    5
    115
  • 胡二
    计数排序中,从数组A中取数,也是可以从头开始取的吧

    作者回复: 可以的 只不过就不是稳定排序算法了

    2018-10-19
    9
    52
  • 姜威
    总结:桶排序、计数排序、基数排序
    一、线性排序算法介绍
    1.线性排序算法包括桶排序、计数排序、基数排序。
    2.线性排序算法的时间复杂度为O(n)。
    3.此3种排序算法都不涉及元素之间的比较操作,是非基于比较的排序算法。
    4.对排序数据的要求很苛刻,重点掌握此3种排序算法的适用场景。
    二、桶排序(Bucket sort)
    1.算法原理:
    1)将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行快速排序。
    2)桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。
    2.使用条件
    1)要排序的数据需要很容易就能划分成m个桶,并且桶与桶之间有着天然的大小顺序。
    2)数据在各个桶之间分布是均匀的。
    3.适用场景
    1)桶排序比较适合用在外部排序中。
    2)外部排序就是数据存储在外部磁盘且数据量大,但内存有限无法将整个数据全部加载到内存中。
    4.应用案例
    1)需求描述:
    有10GB的订单数据,需按订单金额(假设金额都是正整数)进行排序
    但内存有限,仅几百MB
    2)解决思路:
    扫描一遍文件,看订单金额所处数据范围,比如1元-10万元,那么就分100个桶。
    第一个桶存储金额1-1000元之内的订单,第二个桶存1001-2000元之内的订单,依次类推。
    每个桶对应一个文件,并按照金额范围的大小顺序编号命名(00,01,02,…,99)。
    将100个小文件依次放入内存并用快排排序。
    所有文件排好序后,只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。
    3)注意点:若单个文件无法全部载入内存,则针对该文件继续按照前面的思路进行处理即可。
    三、计数排序(Counting sort)
    1.算法原理
    1)计数其实就是桶排序的一种特殊情况。
    2)当要排序的n个数据所处范围并不大时,比如最大值为k,则分成k个桶
    3)每个桶内的数据值都是相同的,就省掉了桶内排序的时间。
    2.代码实现(参见下一条留言)
    案例分析:
    假设只有8个考生分数在0-5分之间,成绩存于数组A[8] = [2,5,3,0,2,3,0,3]。
    使用大小为6的数组C[6]表示桶,下标对应分数,即0,1,2,3,4,5。
    C[6]存储的是考生人数,只需遍历一边考生分数,就可以得到C[6] = [2,0,2,3,0,1]。
    对C[6]数组顺序求和则C[6]=[2,2,4,7,7,8],c[k]存储的是小于等于分数k的考生个数。
    数组R[8] = [0,0,2,2,3,3,3,5]存储考生名次。那么如何得到R[8]的呢?
    从后到前依次扫描数组A,比如扫描到3时,可以从数组C中取出下标为3的值7,也就是说,到目前为止,包括自己在内,分数小于等于3的考生有7个,也就是说3是数组R的第7个元素(也就是数组R中下标为6的位置)。当3放入数组R后,小于等于3的元素就剩下6个了,相应的C[3]要减1变成6。
    以此类推,当扫描到第二个分数为3的考生时,就会把它放入数组R中第6个元素的位置(也就是下标为5的位置)。当扫描完数组A后,数组R内的数据就是按照分数从小到大排列的了。
    3.使用条件
    1)只能用在数据范围不大的场景中,若数据范围k比要排序的数据n大很多,就不适合用计数排序;
    2)计数排序只能给非负整数排序,其他类型需要在不改变相对大小情况下,转换为非负整数;
    3)比如如果考试成绩精确到小数后一位,就需要将所有分数乘以10,转换为整数。
    四、基数排序(Radix sort)
    1.算法原理(以排序10万个手机号为例来说明)
    1)比较两个手机号码a,b的大小,如果在前面几位中a已经比b大了,那后面几位就不用看了。
    2)借助稳定排序算法的思想,可以先按照最后一位来排序手机号码,然后再按照倒数第二位来重新排序,以此类推,最后按照第一个位重新排序。
    3)经过11次排序后,手机号码就变为有序的了。
    4)每次排序有序数据范围较小,可以使用桶排序或计数排序来完成。
    2.使用条件
    1)要求数据可以分割独立的“位”来比较;
    2)位之间由递进关系,如果a数据的高位比b数据大,那么剩下的地位就不用比较了;
    3)每一位的数据范围不能太大,要可以用线性排序,否则基数排序的时间复杂度无法做到O(n)。
    五、思考
    1.如何根据年龄给100万用户数据排序?
    2.对D,a,F,B,c,A,z这几个字符串进行排序,要求将其中所有小写字母都排在大写字母前面,但是小写字母内部和大写字母内部不要求有序。比如经过排序后为a,c,z,D,F,B,A,这个如何实现呢?如果字符串中处理大小写,还有数字,将数字放在最前面,又该如何解决呢?
    2018-10-22
    39
  • 在路上
    我觉着可以把大小写字母根据对应的ASCII值转化成数字,然后遍历一遍就可以了吧。
    2018-11-02
    2
    36
  • Monday
    老师,个人感觉这节没有以往章节的细致了,拿桶排序来举例:
    1、自问的三个问题只有了时间复杂度分析,少了是否为稳定排序算法和空间复杂度两个问题。
    1.1)稳定性,若单个桶内用归并排序,则可保证桶排序的稳定性;若使用快排则无法保证稳定性。
    1.2)空间复杂度,桶都是额外的存储空间,只有确定了单个桶的大小才能确定空间复杂度;n个元素假设分为m个桶,每个桶分配n/m个元素的大小?个人觉得单个桶的大小不好确定,但是范围应该在n/m~n之间
    2、没有伪代码实现,自己在代码实现中遇到了一些问题
    2.1)桶个数的设置依据什么原则?
    2.2)桶大小的设置,让桶的能动扩容?
    望回复,谢谢!

    作者回复: 1)这一节课的重点是应用场景
    2)关于时间 空间 稳定性分析确实没有前面两节详细。不过通过前两节的学习 这三种排序算法的时间 空间 稳定性分析应该简单多了
    3)你说的对 要用归并
    4)桶的大小设置的原则 权衡空间 时间复杂度 在你能接受的执行时间和内存占用下完成就可以 并没有一个标准答案
    5)是的 要么用链表 要么用动态扩容的数组

    2018-10-22
    26
  • seniusen
    计数排序中可以从头向后取数据吗?个人感觉似乎是一样的过程。

    作者回复: 可以的 但就不是稳定排序算法了

    2018-10-19
    22
  • 徐凯
    包含数字的话。其实就是一个荷兰国旗问题 思路与第一题类似 一个指针控制左边界 一个指针控制右边界 左边界控制小写字母 右边界控制大写字母 另外一个指针扫描 遇到小写字母跳过 遇到大写字母则将右边界-1的元素交换过来 此时q指针应保持原位置不动 因为右边还未扫描过 交换过来的元素无法保证就是小写字母
    2018-10-19
    2
    19
  • 伟忠
    以前了解桶排序,以为计数排序就是桶排序的优化,很简单,没想到里面用"顺序求和"快速得出值对应的原排序对象位置(有多个相同值的时候是这个值在排序后的数组中的最后位置,用一次以后减少1),这样就可以用对象属性来将对象进行排序了,这波操作666

    基数排序用了排序算法的稳定性,排多次
    2018-10-19
    17
  • 叶明
    老师,你好,有个疑问:
    在计数排序中,第一次得到数组int[] c = new int[]{2,0,2,3,0,1}之后,
    能不能直接遍历数组c,

    int j=0;
    for(int i=0; i<c.length; i++){
        int count = c[i];
        for(int k=0;k<count;k++){
            a[j++] = i;
        }
    }
    这样不是也对所有的分数进行排序了吗?这个不知道可以不?第一次发言,希望能回复下

    作者回复: 如果你排序的不是单纯的数字 而是一个对象呢

    2018-12-17
    4
    8
  • coulson
    老师,你讲的一会数组C,一会数组R,一会数组A,已经被绕晕了,咋办?跟不上节奏了

    作者回复: 多看几遍 确实不好理解

    2018-10-30
    2
    8
  • Ant
    看了俩小时

    作者回复: 如果之前没基础 想掌握牢固 起码看一个礼拜吧😄

    2018-11-02
    1
    7
  • Kudo
    关于思考题:
    如果分为三个桶(大写、小写、数字),那么时间复杂度应该不会达到O(n),因为O(nlog(n/m))中的m只有3,时间复杂度会退化到O(nlogn)。如果要达到O(n)的复杂度,我认为应该使用计数排序,将A-Za-z0-9作为62个桶,这样遍历一次就可以完成排序。(如果上述理解有偏差,请作者务必指出,多谢!)
    2018-10-19
    2
    7
  • 刘強
    根据acill码的天然顺序,分三个桶就可以把
    2018-10-19
    7
  • 烈冬冰夏
    老师 您好。您说的手机号码排序伪代码向下面这样
    sort(array,comparator)//对比第11位
    sort(array,comparator)//对比第10位
    sort(array,comparator)//对比第9位
    sort(array,comparator)//对比第8位
    sort(array,comparator)//对比第7位
    sort(array,comparator)//对比第6位
    sort(array,comparator)//对比第5位
    sort(array,comparator)//对比第4位
    sort(array,comparator)//对比第3位
    sort(array,comparator)//对比第2位
    sort(array,comparator)//对比第1位

    我不太明白这和直接对比手机号码大小有什么区别
    sort(array,comparator)//对比手机号码

    作者回复: 每一位排序用的是O(n)时间复杂度的桶排序或者计数排序

    2018-11-06
    6
  • 林贻民
    老师你好,觉得计数排序可以完全被桶排序取代,由于计数排序对数据的要求是范围不大,不妨设为k,那完全可以分为k个桶,遍历一遍待排序列,将对应元素放入相关桶中,最后在按顺序遍历一次,即可得到顺序序列.在时间复杂度,空间复杂度上与计数排序一样,但是在代码编写上要比计数排序要简单的多.

    作者回复: 👍 你说的没错,在实践中,桶排序可能更实用些:)

    2019-03-04
    5
  • ning~
    https://mp.weixin.qq.com/s/KU-AUGOnLeRtE_hivl2uSA

    这是一个仁兄写的计数排序,感觉是不是理解简单点?
    2018-11-22
    1
    5
  • kakasi
    桶排序:
    1. 原理: 根据数据范围,分成若干个数据段的桶,通过遍历讲数据放到对应的桶中。每个桶里都进行快排或归并。
    2. 时间复杂度: 最好o(n), 最坏o(nlogn), 平均o(n),一般桶分的越细越多复杂度就会最好。
    3. 内存消耗: o(n)
    4. 稳定性: 取决于每个桶的排序方式,快排就不稳定,归并就稳定。
    5. 适用场景: 数据范围不大的。内存吃紧的,如磁盘的读写可以分成多个小文件并对每个小文件排序,然后直接写到大文件里,这个时候内存消耗不再是o(n)了。

    计数排序:
    1. 原理: 特殊的桶排序,即每个下标代表一个数据范围,其值就是这个数据的个数。
    2. 时间复杂度: 都是o(n)
    3. 内存消耗: o(n)
    4. 稳定性: 稳定,只要整理最后结果时从后开始遍历即可。
    5. 适用场景: 数据范围不大的,如年龄排序。

    基数排序:
    1. 原理: 对数据的每一位进行桶排序或计数排序,对每位排序后结果就是有序的。
    2. 时间复杂度: 最好o(n), 最坏o(nlogn), 平均o(n)
    3. 内存消耗: o(n)
    4. 稳定性: 稳定。否则就排不成的。
    5. 适用场景: 是在桶排序和计数排序基础上进行的,保证每位数据范围不大,并且位数也不是很多。
    2018-11-04
    5
收起评论
99+
返回
顶部