大家好,数据结构与算法这一讲,我们继续第八章内排序的学习。
我们今天的主要内容是分配排序,包括桶排和基数排序。
那分配排序呢,它主要是
不需要进行记录两两之间的比较,
而是根据纪录它自己的关键码的这种分配而来进行的。
因此呢, 我们需要知道记录序列的一些具体的情况,特别是关键码的分布。
我们首先介绍一种桶排。
如果我们知道这个序列里面它的记录
都位于一个比较小的区间范围之内,
那我们可以呢把相同值的记录都给它分配到同一个桶里面,
然后我们依次收集这些桶就得到一个有序的序列。
那我们来看例子。
例如,我们是有这么几个记录值。
那我们观察呢,它的关键码分配呢, 大概是在0到9的范围之内。
因此呢,我们就设10个桶,每一个桶
我们可以估计一下,它大概会有几个元素。
然后呢我们把这些相应的元素分配到各桶里面就可以。但是
如果你这个桶呢是需要物理的再开辟一个区间的话呢,那样比较麻烦。
我们最好是借用整个这个数组的
位置,桶呢它实际上是一种虚的桶。
那我们每一个桶呢有预留的一定的位置,然后我们把这些相应的数据存进去,
那收集起来呢就是一个有序的。而那这样的话呢需要看一下,
在每个桶的计数之上,
我再看看我前面若干桶总共呢会有多少个元素。
因此呢我们就进行这样的一个累计的计数。 那对于第0桶,那它本身只有0个。
然后呢,这个第1桶加起来是有两个元素,
那前面呢元素为0值和1值和2值的加起来有3个。
那依次这么累加,我们就得到这么一个对桶的一个计数。
基于这样的一个计数呢, 我们就可以来排序了。
那这个排序的过程,我是把这个代[排记录呢,我从
右往左来扫描。
那因为我们前面已经对于每一个桶
都得到了一个它的累积的计数,比如说我现在看到数值2的时候我知道
它的累积计数呢是3。 那因此呢就是说,在整个已排的这个数组里头,它前面有3个
元素。因此我们这个2呢,就可以排在整个数组的第3个,
也就是下标为2的位置。那我们把刚才那个计数3减1然后得到
这个下标,而且呢这个计数呢同样它要减一下,再保留在这个
累积的这个计数桶里面。 那我们再看这个1‘,那我们之所以
说它是1‘,是因为前面有个1,它是第2次出现的1。
那我们查这个表里面呢,
就是得到的是元素位置呢是2,
那也就是说前面有两个元素是在这个1号桶里面的,之前的这些位置。
那因此呢我们把这个1‘呢就摆在这个数组里面的
第2个元素,也就是下标为1的这个位置,而且这个计数呢也是减1。
那我们再看这个8,它也是8‘,那我们查这个表,
它是在前面一共有累计
8个这样的数据,所以呢它排在这个数组下标从0
到7这个位置里面呢相应的是在7这个位置,那我们也是把计数再减一下。那我们再来看这个
1这个元素的时候呢,
它一定是排在1‘之前的, 以为我们先把1‘在整个这个
标号为1 的相关的这个序列桶里面,它是排在最后一个元素。
那我们在看到1的时候呢,它查这个累计
count这样的一个计数呢就会查到是,下标呢是
1之前的那个位置,就是0。
因此呢我们就保持了它的一个稳定性。
那其它的元素呢,我们也是依次这样的处理。
最后呢就得到了一个有序的序列,而且它是稳定的。
桶排的算法呢,我们在这个前面是做一些初始化的工作。
然后呢,在这里我们是从0到n减1位
逐个扫描这个输入的元素,
然后呢,它,这些元素呢都落到相应的这个
桶里面,也就是这个相应的桶呢它的计数个数会加加, 因此这是一个o(n)的一个扫描。
然后我们把这个count数组呢,再
继续的加工,那我们把前面若干个桶里面的这些元素
个数都加起来,作为当前这个count数组的一个当前值,也就是说,
我们得到的是小于等于i的元素个数
一个总和。得到这个总和呢就是根据我们刚才这样一个排序过程我们就知道,
我们从这个数组的最右边,也就是n减1,往最左边,也就是0,
一直处理,得到一个元素呢我们在这个
相应的这个count数组里头去查表。
然后得到那个值呢,我们先减减,
然后我们把你当前要处理的这个元素呢,
我们把它放到这个相应的位置。整个这样的处理完了以后,
就是一个有序的数组,而且呢它是稳定的。
我们看一下这个桶式排序它的算法的一些性能。
首先呢,就是时间代价来说呢我们主要是分为几个
部分,那统计计数呢,我们对于每一个元素都要扫一遍,因此
它有这个θ n的这个时间。 另外呢,我们对这个计数数组,我们还有一个
对它前面的若干的这个桶的总体的元素个数呢
有一个求和。因此呢是一个θ m的时间。
那我们把查看这个元素个数的时间再加上这个
桶的计数的这么一个累计的时间,就是θ (n+m)。
对于这样的一个桶排,
还有这样的个时间代价,我们显然可以看到呢,
一般来说我们是适合于这m相对于n来说很小的情况。
如果是说m它比n本身还大,
或者是它的范围非常非常的大,那我们所需要的这个桶的个数
就很多了。这样是不太划算的。空间代价呢,我们最主要的是
有m个计数器来记录桶里面的元素个数
以及桶的这个累计的这样的前面若干个元素的个数。
那另外呢,我们
要开辟一个长为n的临时数组,主要是用于
把这个桶排的这个数据呢从一个待排的这样的一个数组呢导到这个临时数组里面,
然后我们在这个结果的时候呢,就用你这个待排数据的那个数组。我们再把这个临时数组里面的
这样的相应的元素给它挪过去。因此呢我们的空间代价呢也是θ
(n+m)的。
那刚才我们看到它的一个算法过程是稳定的。
另外我们再有几个思考的问题。首先就是说,如果是桶排的情况,
那我们这个m多大合适?如果太大怎么办呢?
还有呢就是桶排里面我们这个count数组它是干什么用的?
另外我们为什么要从后往前来收集这个数据?
那其实我们前面也回答过这个问题。谢谢大家。