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

精选留言(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