大家好，数据结构与算法这一讲我们继续
第8章内排序的学习。因为桶排只适合m很小的情况，
那如果m确实是很大，甚至大于n的情况，怎么办呢？
那我们就可以想像一下，如果我能够把这些
记录的关键码给它人为的拆分为几个部份；
那我，嗯， 运用几次桶排，就可以完成这个排序了。
基数排序呢它其实就是这么一个思想。让我们首先来看一下基数排序
嗯，它的一个定义。对于这个，嗯， 排序码k呢，我们人为的给它拆分为第一个这样的
子的排序码。这个K的d-1呢是最高位的。那K0呢？
就是，嗯，最低位的。嗯，如果这个序列对于这样的一组排序码有序呢？
那么就是说，这里面对于任意的两个记录Ri,
Rj ,如果是i小于j的话呢
它相应的这个组和关键码呢也是，嗯，要小于，嗯，另外一个的。
我们可以看到，嗯，对于这个，嗯，组合关键码的情况，其实嗯，最高位
它的分辨的，这样的一个，嗯，优先基数最大的，如果我们在最高位就确定了他们相对大小，那就基本上
这两个大小就确定了。那如果一直到这个0位
嗯，他们还是相等的，那么这两个记录它们的排序码是
相等，当然排序码相等，并不一定是说这个纪录是相等的。有可能
就是我们说的有重复的，嗯，排序码的情况。但是，
它的记录里面其他的信息可能不一样。比如说，我们排序码如果是人的姓名，
那两个人同名同姓，但是呢它可能是不一样的人。他有其它的记录呢能够区别这两个人。
基数排序我们可以看到我们怎么人为的来划分这样的一个
嗯，长的，嗯，排序码或者是说这个m范围比较大的这样的排序码。
那如果是说，对于0到9999这样的一个数据范围。
那如果我们是按照个、十、百、千
这样来划分，当然如果我们从高到低的是千、百、十、个
这样的划分。这样的话呢？我们就可以把它变成四趟排序。
那如果是在这个最高位已经确定了它的相对的这个大小，当然就，嗯，完成，对吧？那如果是，嗯，
在，嗯， 次高位， 嗯， 它还需要进行比较，那我们再逐个儿逐个儿的去划分。
因此呢，嗯， 这就是说什么叫做基数排序。我们其实这里呢
就把它这个radix，嗯，作为10。那我们，嗯，这样的
以10为基数来进行划分，那把这个数值就分成，嗯，4段。
那我们载来看一些符合的，嗯，排序码的情况。嗯，
比较典型的例子就是扑克牌的排序。那我们假设，扑克牌呢
我们首先以花色来判断它们的大小，那同一种花色呢
再看他们的数值，也就是，嗯，面值的这个大小。
那我们如果对这一组数据需要进行排序，
首先呢如果我们按照高位先排，嗯，那我就可以用递归分治的这种方法。
如果是按照，嗯，这个从小到大这么一个正序
的序列，那我就是草花，嗯，
是在最前面，然后再是方片；再是红心和黑桃。
那花色分完以后，在每一个这个值桶里面呢
你只要管你自己那部，那，嗯，他们这个不同的，
嗯，花色块儿与块儿之间，它已经是有序的了。那我们接着呢再按面值来给它排。
那其实这个过程呢它是一个递归分治的这么一个过程。
那如果我们按照低位先排，
那在这种情况下呢，我们特别是要注意 你的排序方法。嗯，最好是要稳定的。
那我们，嗯，对于这个面值，我们先排出这样的一个序。那我们可以看到， 在这里面呢，3
这个面值里面我们有两张牌。
再按照花色来排，这个时候我们只看这个花色；不要再去看面值。
那对这种情况， 我们看到的这个草花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。
它要存放整个待排的数据。
呃所以是一个嗯么θ（n）的空间。另外，我们需要
用到r个桶。这个桶呢，我们其实主要是体现在
计数器的这么一个作用。那我们实际的那个桶啊，
还是在那个TempArray里面，啊，我算出它的一个逻辑的
这样的一个数据间隔。那这个间隔呢就是存在这个计数器里面。
啊然后我们是把数据呢存在那里面去，
并没有真的去开辟某一个桶空间。
那总的空间代价呢是θ（n+r）的。
我们的时间代价呃其实呢对于一趟桶排，
它显然是要扫描这些数据它的相应的那个第i位，对吧。
然后呢，要对这个呃计数的这个数组呢，进行相应的操作。
那它的时间代价，一趟呢就是θ（n+r）。
但是我们在啊基数排序里面，我们是人为的给它切分为d个数据域，
呃组合成为一个组合型的排序码。
因此呢，我们要做d趟这样的桶排。
它的时间代价就是d*（n+r）。
然后我们再来看这么一个算法。大家想一下，
哎看起来似乎很像我们前面的桶排。
好像有一些不一样的呢就是说，呃它计完数以后就直接只需要
根据这个计数的这个情况，然后呃来把这个相应的这个数值呢给它输出去，
就行了。但是大家思考一下，它排了什么东西吗？
它好像就是把这些数值给你输出来。
那如果我们待排的这些元素，它除了排序码以外， 它还有一些其他的信息，那
用这样的一个框架它能完成桶排的算法吗？
似乎是不可以的。谢谢大家