再按照花色来排,这个时候我们只看这个花色;不要再去看面值。
那对这种情况, 我们看到的这个草花1 和草花8其实都是草花。
你可以看到草花8呢是它第二次出现,按照我们的惯例我们把他打上一撇。
那你如果能够 保证它的一个稳定性的话呢,你前面
嗯,草花1它按照面值已经是一定在草花8之前。
那我们如果是在按花色排它还能够保证稳定性,
那就一定是草花1在草花8之前出现。
这就使得我们整体的排序呢它会是一个有序的。
其实这里面有一点,我们在第一趟的时候
不那么严格的要求它一定是稳定的。
就是在第二趟以后的其它趟的排序一定要保证是稳定的。那我们,嗯,
来看一下刚才我们说的这几种方法。 其实我们把它分解,就是这么一个过程。就是先按
最高位排,排到若干桶,每个值桶里面再分成小的值桶。
一直排到,嗯, 最低关键码。
那这个过程呢其实是一个分,分,分,分,收
这个过程。而且,收呢不是那么明显。就是假设你这个桶
都是有序的,放好的。它个个跨值间
它是分别有序的。那最后这个收呢是一个很显然的过程。
那我们再看这个低位优先的方法,它是先从最低位开始排;
然后呢,排好以后呢,再按照次低位接着排。一直到这个最高位都排好了为止。
那我们这个排的过程呢 其实每排一个,都是要先分,
嗯,就是分到不同的桶里面,然后呢,再把它收集整理起来。
然后就是分、收、分、收、分、收这么若干趟,最后就完成了排序。
那低位优先法呢,我们人看起来是比较实不太好懂的;或者是说看起来挺别扭。
嗯,高位优先呢我们处理起来是非常方便的,因为它是一个自顶现像的思想。
但是,低位优先呢在计算机处理的时候,非常的高效。嗯,这一讲呢
就是介绍低位优先的这些相关算法。
那我们看一下,基数排序的这样的具体的实现。
那我们讨论顺序的方法和链式的方法,这两种算法。
那我们来看一下顺序的方法。那其实呢
我们就是反复的利用桶排。例如,嗯,我们对这么一组数据
那首先呢,我们就是,嗯,对这个个位呢进行一个排序。
那这个过程就跟刚才的桶排是一样,那但是我们第一次呢,只看个位。
那我们按照个位来划分,首先是
一个基数,然后呢,我们再分配到这个相应的桶里面。
然后我们,嗯, 收集呢就是把它,嗯,
分到,嗯,最相应的这个桶里面去。但我们这时候不能看它的
十位;只能看个位。我们看按照个位是有序的,1、2、3、6、7、8、9。
这个结果,我们继续进行这样的一个桶排。
这时候呢,我们只看十位;不看个位。
那,嗯,类似刚才的这个分配过程,排的结果呢这时候我们
也是只看它的十位,不去看它的个位
嗯,但是大家要注意,我们第二趟以后呢,
一定是要用稳定的排序方法来进行。
那因此呢能够保持
刚才我们个位分出来以后,它的一个相对的顺序。那我们
最终呢就得到一个正确的排序结果,而且这个排序结果它是一个稳定的。
那我们来看,基于数组的基数排序的一个实现。
那这个前面呢就是一些初始化的这些工作了。
那我们这里特别注意呢,我们保留了一个Radix 这么一个模进位的这么一个变量。
嗯,它用于我们来取这个第 i 位
的那个数值。嗯,首先呢我们对第 i 个排序码呢进行分配。
那,嗯,在对这个第 i 位,嗯, 进行分配的时候呢
我们,嗯,统计,嗯,每个桶里面的记录
个数的时候,我们恰巧只能取当前这个第 i 个排序码。
那我们这里做的一个运算呢就是,啊首先呢
我们呃对于这个待排的这样一个元素呢,
我除以这个Radix。其实就是, 把它右边的这个若干位给它去掉。
然后呢,再对这个呃基数这个r呢
呃进行一个取模的操作,就把它的
左边的就是高的那些若干位去掉,就正好取到这个第i位。
然后我们得到这个k值呢,在这个相应的k桶里面,它的这个计数个数就是++。
然后我们再给这个桶划分下标界,实际上呢
就是说,我们来统计一下在这个第i位的时候,
标号为j的这个桶前面的若干个桶的这些元素总和是多少。再加上它
自己的这个元素总和。这个得到这个数值呢,我们在后面分配的时候就可以利用起来了。
呃那我们接着就开始分配。 我们是从这个数组的尾部,也就是从右边往左边来进行收集的。
那我们呃从右边往左边进行收集的时候呢,呃我们也是跟刚才
类似,就是我首先取到k值,就是当前的这个元素啊它在
第i位的那个数值,然后查这个相应的这个桶计数的那个值。
然后呢,因为我们前面记的是一个累计的这个数值,
所以呢我们把这个数值呢,减减以后就是我们当前
在这个结果的数组里面应该排的那个下标位。找到这个下标位呢,
那我们就是把我当前这个待排的这个数组元素的值呢,
就放到相应的这个结果的这个元素数组的相应下标。排完以后,
那我们最后要记得把这个呃内容呢,
复制回到这个Array这样的一个数组。也就是说,我们在整个排的
过程中呢,这个Array和TempArray 它是互相,这个数据导来导去的。这样
使得我们的整个排序过程呢更加的便捷。
呃然后我们要记得在这一轮啊排完呢,把这个Radix呢
要乘以r,也就是说,我们现在往前面进位呢,推进了一位。
啊比如说,我们如果这个r是10的话,那我们第一次r是等于1。
那就是在个位上取。第二次呢,就是Radix呢乘以这个10就等于10,那就在十位取。
然后在下一次,再乘以10就是等于100,就在这个百位上头取。是起到这么一个作用。
那我们分析基数排序它的呃一些空间和时间的代价。
啊首先呢就是在空间上, 啊它们是要用到这样的一个大的临时数组,就是我们前面看到的那个TempArray。