线性排序

Monday, April 22, 2019

桶排序

核心思想是将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序。桶内排完序后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序了。

file

  • 桶排序的时间复杂度是O(n)

  • 桶排序时间复杂度很低,但是不能替代快排或者其他排序方法

    1. 桶排序要排的数据要很容易就划分为m个桶,并且桶与桶之间有大小顺序。
    2. 其次桶排序要求数据在各个桶之间的分布是比较均匀的。极端情况下,所有数据都在一个桶里,就又退化为nlogn了
  • 桶排序适合用在外部排序中,数据量比较大,内存有限,无法将所有数据全部加载到内存中。

比如我们要降10GB的订单数据按订单金额排序,内存有限,没法一次全部加载到内存中。

  • 我们先扫描一遍文件,看订单金额范围,假设最小是1元,最大是10w元。我们将说有数据放到100个桶里(1-1000,1001-2000以此类推),每个桶对应一个文件,按照金额范围的大小顺序编号命名。
  • 理想情况下,订单金额均匀分布,每个桶100MB。
  • 但是正常情况下,一定是会有某些区间特别多数据,我们可以继续在这个区间进行划分,直到所有文件都可以读入到内存为止。

计数排序

  • 计数排序是桶排序的一种特殊情况 当要排n个数据,数据范围是k,我们可以划分为k个桶,每个桶的数值都是相同的,省去桶内排序。 比如我们要将50w考生的成绩排序,总分900分,我们就可以划分901个桶,将学生成绩划分进去。时间复杂度只要O(n)

计数排序详解

我们用8个考生,分数在0-5来举例,考生成绩是2,5,3,0,2,3,0,3

  • 我们将考生放到一个数组A[8]中。
  • 将成绩放到大小为6的C[6]中,c[6]存储的是对应的考生个数
  • 我们对c[6]数组顺序求和,c[k]里存储小于等于分数k的考生个数

file

我们从后到前依次扫描A数组,比如第一个学生是3,我们查看C数组对应下标3的数据,是7,说明包括自己在内,前面有7个数据,这样我们就将3放入到排序数组R里的7下标,R[7]。依此类推。

file

基数排序

假如我们要排10w个手机号码,该如何排序,比快排更高效的方法就是基数排序。

桶排序,计数排序不适合排手机号,因为手机号有11位,范围太大。

手机排序有个规律,如果前面几位已经比后面大,那就不用再排序了。

我们借助稳定排序算法,先排最后一位,再排倒数第二位,以此类推。

根据每一位来排序,可以用桶排序或者计数排序,时间复杂度为o(n),如果数据有k位,则是o(k*n),k不大时,就近似于o(n)。

总的来说,基数排序对排序数据是有要求的,需要可以分割出独立的位出来,而且位之间有递进关系,此外每一位的数据范围不能太大,要可以用线性排序来做,否则就做不到o(n)了。

数据结构-算法

排序优化

排序(下)