大家好，数据结构与算法。
这一讲我们继续第八章内排序的学习。
我们再来看基于静态链的这么一个实现。
那我们如果把分配出来的子序列呢，
存在这样r个静态的队列里面。
那这个每一个队列呢，
它就是相当于一个桶。而且因为它是真的给它拉出来的一个队列，
所以就跟我们刚才，还把它放在这个数组里面，
它的一个虚拟的，这么一个桶的区间那不一样。
那我们真的是有桶拉出来了。
这里呢注意我是用的静态链。那也就是说，
我用的是一个数组的相对的下标。而不是真的
去给它用出来动态的这种指针数组。因为如果我用出动态的指针数组的话，
它的空间会有比较大的浪费。
那我们来看我们这个，一个演示。
首先呢，是对个位进行一个桶排。
那很容易，我这里分成十个桶，因为我们是十进制的这样的数据。
那我从左到右相应的去分配这些元素。
那97就分配到标号为7的这个桶。然后我接着分59，26。那每一个元素呢，
我们为了保持它的一个稳定性呢，
是一定要加到这个，桶的这个队尾里面。
也就是说我们这个桶是用队列来表示的。
你新加的元素一定要放在队尾。
这样的话呢，我们在收集的时候，把这些队列呢， 首尾相连，给它顺起来，
它就成为一个，针对这个个位是有序的这么一个序列。
现在我们还没有完成排序，因为十位还没有处理。
那继承刚才个位排序的结果，我们现在呢，
只看十位，不看个位了。那么，我把所有的元素都相应的，
分配到它的桶里面去。
这个结果也是我们把这些非空的桶，
给它首尾连起来，就形成了一个排序的结果。
因为它已经是第二趟，也就是在这个待排的数据里面呢是最高位。
那我们就完成了这个排序的过程。而且我们要注意，
第二趟你一定要继承第一趟的这个排序的成果，
那必须是采用稳定的排序方法。我们来看这个
静态队列的一个定义，以及我们这个基于静态的，
这样的指针的一个结构。
我们实现基数排序。
那为了方便起见呢，我们把代排的这个元素呢，
就直接扩展一位。就是，它是表示呢，
在这个元素的这些链接的结构里面呢，
它可以指出来我的下一位是谁。
它其实就形成了一个单链的这个结构。
其实只用了next来指向我的下一位。
而且这个下一位呢，它其实就是我们的这个下标的这个值。
它下面一位的下标是什么，我们就存在这个next值域里面。
那因此呢它是一个静态链的一个结构。
我们的队列呢我要保持它的队首和队尾的指针。
这里面呢，它也是，
只是一个下标的这个值。那我们再看基于这么一个静态链的基数排序的实现，
那前面呢也是一些初始化的工作。这里面我们特别注意呢，
我们从头开始。
然后我把整个，原来它是一个数组，
但是我们加了这个next域以后呢，我把这个数组里面的元素，
前面一个跟后面一个呢，就这么串接起来。可以看到，
我就是next就等于i+1。就是我当前这个Array
i的next等于i+1。
就把这个整个这个数组呢，就这么勾起来了。
然后最后那个元素它的next呢，等于负1。
就表示我在这里是我的队列的最后一位。就是相当于我们，
在动态的指针里面的那个null，
那样的一个功能。然后我们对第i个排序码，进行分配和
收集。因为我们把这个整个排序码呢，分成了d个段。
所以我们这里呢，一共是要进行d趟的这种分配和收集。
分配收集呢在后面我们会给大家再介绍。
那我们经过这样的分收分收，总共d趟，
然后得到一个结果的数组。但是呢，大家注意，
我们其实因为我的排序，只是在这个，
静态链的基础上进行的。所以我们得到的那个数组呢，它会是这些指针域，
这样串起来的，来表示他们的这样的一个相应的顺序。
我们整个这个array呢你从0到1到2，这样的一个下标来看，
看这些数组的元素呢，它其实，
并不是有序的。而是要通过next那个域互相连起来有序。一会我们可以看到这样的例子。
因此呢，我们再排完以后呢，要有一个整理的工作。
就是根据这个next域的一个索引的信息，
然后我把这些元素呢，整个整理好。让它存在这个array里面呢，就是
根据这个下标会是有序的。
同时呢这个next域，其实我们不一定是非要跟这个原来数组里面的，
排序码放在一起作为一个这样的节点。
我们其实是可以单独再拉出一个这样的专门对它的一个，
next域的链。那就是跟array呢是一个平行的数组。你要注意他们的，
这些下标的对应。当然那个实现可能看起来麻烦一点。
所以我们这里呢是把key和next放在一起来看。
那我们来看这个， 静态链的基数排序的算法。那首先呢，
我们这个current呢，是
先把它表示为整个代排数组里面的第一个元素。
然后呢我们把每一个桶呢都赋为空。
然后我们顺着current它指向的这样的一个
数据以及它们相应的next链，
拉出来的的单链表。我们逐一的来取这些待排的元素。
那首先呢我们是把这个当前，
这个元素它所指的这个排序码指出来，
然后呢，放到k里面。然后呢，我们是取这个
第i位，它的这个 排序码。那我们取第i位排序码呢，
其实跟我们前面所讲的，利用radix那个是类似的。
那这里面呢就是说我们是传入的是， 对当前第i位来取这个元素。因此呢，
我们这里呢是对它除以i次，
这个基数。其实就是我们把这个
尾巴的那个若干位呢给去掉，
也就是说，若干个低位这里其实是i个这样的低位，
去掉。然后呢这边再取摩，
把它的左边的若干高位去掉。也就是正好取的是第i位。
然后我们把这个数值呢，
放到相应的第k个桶里面。
第k个桶如果是空的，它就是第一个元素。
否则呢，我们把它放在这个第k桶里面的队列的尾巴，
而且呢我们把这个第k桶的这个队列尾呢，
现在这个指针指到当前这个current。
然后我们这个current呢，它自己又指向这个array里面，
待排的元素的下一位。这就是一次分配。
那我们再来看一下这个收集的过程。
那这个收集呢我我们其实就是把这些非空的这些桶，
它们首尾相连起来，就完成了收集的过程。
首先我们要找到第一个非空的桶。找到了以后呢，整个这个结果它的队首，
就是指向这个第一个非空桶它的头。
我们现在把这个last呢指为第一个非空桶它的尾。
然后接着再找下一个非空的桶，然后我们把这个下一个非空的桶呢
接到我们刚才，哦，前面那个非空桶，
啊，它的尾部。啊然后我们这个last呢，顺着往后面走。
那一定要注意呢，我们最后收集完了以后，最后那个last位置，
它的next域，一定要是等于-1，相当于我们
对一个单链表它的最后一个元素呢，next域要赋为空。
那，使得我们在后面进行一些运算的时候呢，能够保证这个
队列的查找工作，它见到这个null，
也就是-1,它能够停止。那我们看一下，
链式基数排序它的算法代价。
首先呢，哦，它有n个记录空间，也是用来倒换这个数据的。
另外呢，啊，也有r个这样的桶，啊，它这里是
表示为队列的头为指针，所以这一对，那总体来说呢我们是
θ(n+r)，这样的一个空间代价。
时间代价其实跟我们刚才的顺序的 基数排序类似，那我们是把它分成d趟，
每一趟呢，我对这些待排的元素都要看一遍，所以是
n这样的一个代价。再加上我对这个，哦，
r个这样的桶呢，我也都要扫一遍，把这个
桶呢，我是分配的时候是给它分进去了，那我在
收集的时候呢，也要首尾相连，把它串起来，啊，因此呢，
它就是一个θ，d乘以(n+r)，这么一个代价。
我们看到它的代价似乎是
啊，d乘以n。而d呢，好像是一个比较小的数。
那我们是不是可以说我们的算法就是一个线行的，也就是说θn
的。
但其实不是那样，因为我们这个d呢，可以说它还是依赖于
n。我们可以想像一下，如果没有重复关键码的时候，
我对n个不同的这样的数据要来编码，
那我一定是需要这个d位的话呢，是以，啊，
r为底，然后这个n的对数，就d一定要大于等于log n。
这样的一个值呢，可以说它还是在Ω（log n)里面的，因此
总体的代价呢，我们带进去来看了，还是n乘以log
n。
然后我们来思考一下，这个顺序和链式基数
排序，它的优劣各是什么样的，你喜欢用哪一个呢？
啊，还有一个问题，就是链式的基数排序，它排完以后的结果啊，
其实，你原来给的输入这个key是这个样子，
然后，在这个，next域里面呢， 会有这样的相应的这些值。
它其实通过这个next的域呢，把
这个数据，它们的一个相对的
大小顺序呢，是能够指引出来。比如说我们
最小的这个元素是在下标6这个位置，就是，
啊，这个元素的值呢，是13。然后，
啊，下标6它的next域是7, 那也就是说次小的是27。
那我们通过这个next域，一个个的去履。我们可以得到一个
从小到大的一个，啊，有序序列。
但是呢，我们可以看到，
这个数组本身，它并没有改。
那如果我希望返回的是个数组，按照这样的下标呢，就有序，也就是说，
13这个元素正好就放在这个，啊，
下标1，甚至我们放在下标0，看你怎么样的一个需求。
放这个位置里面， 然后输出来。
那我们应该进行一个什么样的整理呢？ 这个呢我们在下一讲，地址排序里面会给予介绍。
谢谢大家。