大家好！数据结构与算法这一讲的内容是
第八章内排序。今天我们介绍索引排序。
那前面我们介绍的基数排序它所得到的这么一个结果呢，
它是把这个排序的顺序存在这个next域里面。
而它的数值呢，本身原来是什么样还是什么样。
那我们如果希望排完序以后就按照这个下标，
把这些数值整理为有序的这么一个结果，那我们就需要一个算法来进行整理。
那我们开始呢，可以把这么一个
j指针指向这个结果里面的最小的那个元素，
我们可以依次来处理，来得到第i个
这个元素。那我们首先呢，把当前的这个
结果里面第i个这个元素呢存在 这个临时变量Temp里面。
然后呢，我们把占据了这个下标的第i位的这个元素
和我们真正应该是待在这个第i个这个位置的
这个元素呢我们给它进行一下交换。
同时要注意修改我们这个
已经调整到位的这个
第i位的这个元素，它的next域是
指向它刚才过来的那个j的那个指针。
那也就是说，我们保留了这么一个交换轨迹。
然后，我们现在要处理的这个第j个这个元素呢，
我们又是顺着刚才保留的这个TempRec
它的next域，那我们就是移到了下一位的这样一个待处理的元素。
那如果我们得到的这个j呢，它是小于等于i的，
那表明我们所得到的这个j呢，它其实是
一个轨迹。我们要顺着这个链呢，去找，
找到实际需要处理的那样的一个j
的一个位置。然后我们一直这样的循环进行， 就能够在θ(n)的时间内把这个链整理好。
那结果呢就是按照我们的下标位从小到大排序。
如果我们排序的时候发现这个数据域特别大，
那因为我们排序时间呢主要是由这个记录之间的比较时间
以及我们移动记录了这么移位时间来组成的，
那对于这么大记录的情况呢，如果我们移位很多，那它的时间开销是很大的。
那我们能不能够在前面加一个索引？
那我们发现这个记录需要进行交换或者是赋值的时候呢，
我们是 只对这个索引呢进行，而不整理这个数据域。
那我们排序的结果就保留在这样一个索引数组里面。
那最后呢根据这个索引数组来一次地整理这个数据域。
那我们可以节省排序的整体时间。
那我们来看一下刚才这样的一个
示意的话呢，我们对这样的一个排序的
一串记录，那我们结果呢就放在这么一个索引的数组里头，
那如果我们能够开辟一个新数组，
那我就能够知道，比如说，这个在下标第0位应该是放
现在下标5的这个位置的数据，那我就直接从这边拿过来，
然后我们依次这样处理。那也是在θ(n)
的时间内完成了这个整理。但是它的空间代价是比较大的。
其实我们不必要新开一个空间，那我们后面会给大家介绍一个整理的方法。
那 我们得到的这样一个索引排序的方法，其实
对于我们前面介绍的这些内排序的方法呢，都是适用的。
那我们只需要把那些赋值或者是交换这样的操作呢，
改变成为对我们的索引数组的操作。当然相应的对这些记录的
关键码进行比较的时候呢，也要对这个索引域所指向的
那个相对的这样一个元素的进行比较。
那我们看一下插入排序，我们怎么样对它进行修改，
来变成一个索引地址排序。那首先呢，我们把
这个索引数组呢，都是它的这个下标域，
指向自己，也就是说我自己就待在自己该待的位置。
然后我们可以看，下面是一个插入排序的经典的框架。
那我们当前要处理的是第i个记录，
那我们前面0到i-1呢，它都是已经有序的。
那我们把这个第i个记录要插入到前面一个合适的位置，
那所谓这个合适的位置呢，就是我这个待处理的这
第i个这个元素呢，跟前面这些已排序的元素逐个比。
如果我发现逆置对呢就交换，那一直交换到
某一个元素它跟我当前要处理的这个第i个记录
它是正序对，然后呢，当然前面的那些呢都是逆序对。我们发现正序对，我们就停止。
那 我们注意在这里我们的交换当然是要对
这个索引域里面呢相应的这个元素来进行的，
也就是说我们对索引进行，而不对这个数据域里面那个数据本身进行。
然后我们在比较的时候呢，也是比的相应的
这个索引域所在的那个索引下标它指向的那个数据所在的
那个关键码的值。那我们
比完以后呢，那我们就
会得到这么一个插入排序的一个正确的
它的一个排序结果。但是结果呢，是保留在这个索引域里面。
那我们需要对它进行一个顺链的 一个整理。那我们来看这个整理的过程。
如果我们不再开一个大数组，我们怎么样顺链来进行。
那首先我们在下标0这个位置我们说应该放入
下标5的这个数值。那我先把这个下标0位置
它的这个记录呢先存起来，然后把下标5这个元素给顶过来。
然后呢，下标5的这个位置它要放下标4
位置的这个值。那我们这个34’也顶上来，那相应的34顶上来
然后呢我们在这个下标2这个位置，它说要放下标0这个数值，
那我们这个下标0的这个29呢顶上来。
那因为我们前面已经存在那儿了，那我们就把它拿过来就行了。
那现在呢，它就完成了一个子循环。这个
结果呢，就都分别调整到位。那我
接着呢再去看下一个没有处理的这个元素。
那
这个25呢，它已经待在合适的位置，我们接着
就再看下标3这个位置。那它又是有一轮子循环。
然后我们就给它调整到位了。
那我们来看一下这个整理的一个算法，
首先呢，我们就是按照这个下标0开始到下标n-1，
顺着进行一个单程循环的处理。
那在这里面呢，我们有若干的小循环了。
那我们当前的这个
第i个元素它的下标，我们先给它保留在j里面。
而且把它的这个元素值呢，给它保留在这么一个临时变量里面。
那如果我们这样的一个索引域它所指向的这样一个下标呢，
不等于i的情况， 那这个时候呢我们就把这个相应的
后面我们需要给它填到当前这个
进位的这个数值呢，我给它往前移过来。
而且呢，我们要注意，要相应地修改它的这个索引域的下标。
那
我们这样的一层小循环运行完毕的时候呢，其实就是我们
刚才看到的我回归到索引域的下标等于我们最开始起始的下标的时候。
那这一层小循环就完成。啊，那完成以后呢，
我们这个前面存的那么一个临时的纪录，我
就可以填入了这个，哦，
倒数的那个最后处理的那一个纪录。那，
哦，同时呢，我们要注意把这些下标域呢，也进行相应的修改。
那我们这个循环在下一次进行的时候呢， 我们也是，如果，你这个纪录已经调整到位了，
那你相应的这个下标域呢，它的这个索引值就是自己。
那就不需要处理，所以我们这个循环不会反反复复拉锯地进行。
我们就是一轮扫描过来，已经处理过的它不参加，后面的继续处理。
那我们还有第二种索引方案。
那这个第二种索引方案呢，我们可以看出就是说在这样的一个索引域呢，
是表示的，我这个元素本身应该待在哪一个下标位置。那比如说
29这个元素它因该待在下标2这个位置。我们另外开辟一个数组的话呢，
也是能够单遍地扫瞄，很快地就把这些元素就填充到位。
嗯，但是这个是比较浪费空间的。
那我们，嗯，可以类似于第一种这个方案，
我们也是不需要在另外开辟一个大的数组。
就利用这些索引域来进行整理。
那，嗯，开始的时候我们发现这个，嗯，
29这个元素，哦，那它是应该待在下标域2这个位置。
那我就，嗯，把这个下标域2的这个元素呢，先放到临时变量里面，然后29填过去。
那，这个下标域2的这个位子呢，它说，它自己应该放在下标域4，那我就也往前头挤。
那这也是有一个小的循环，一直
在回到了这个我们开始的这个位置，那我们
这一个数据呢，也是有3组这样的小循环。
那我们依次来处理这些数据呢，那就整理好了。
那最后呢，给大家留几个
思考题。啊，首先呢就是我们证明一下，
前面介绍的这些地址排序的整理方案，它都是在θ(n)的时间可以完成的。
还有呢，我们介绍了说第一种索引的方法，
对于我们前面说过的这些内排序的方案呢，我们都可以试用，
啊，我们只需要对它进行一些小的修改。那我们尝试一下，修改
快速排序，我们在排序的过程中呢，我们不交换
这些数据域而只是对索引进行一些操作。在
排序完成了以后，我们进行一个θ(n)的一个索引整理的过程，然后
得到一个按照我们的下标有序的一个，哦，排好序的一个数组来返回。
那，另外呢就是我们可以查一下这个Rank排序的方法。
我们通过这种方法呢，能够得到第二种索引的这样的一个数组。
嗯，还有呢就是，哦，我们在上一讲介绍的这个静态链的基数排序。
那它的这个结果呢，其实我们可以进行一个特别简单的
一个变换，就得到了我们说的第二种索引的方案。
好，谢谢大家。