1 00:00:01,403 --> 00:00:04,598 大家好!数据结构与算法这一讲的内容是 2 00:00:05,053 --> 00:00:08,399 第八章内排序。今天我们介绍索引排序。 3 00:00:09,167 --> 00:00:14,436 那前面我们介绍的基数排序它所得到的这么一个结果呢, 4 00:00:15,114 --> 00:00:20,913 它是把这个排序的顺序存在这个next域里面。 5 00:00:21,859 --> 00:00:25,475 而它的数值呢,本身原来是什么样还是什么样。 6 00:00:25,761 --> 00:00:31,348 那我们如果希望排完序以后就按照这个下标, 7 00:00:31,651 --> 00:00:39,392 把这些数值整理为有序的这么一个结果,那我们就需要一个算法来进行整理。 8 00:00:39,878 --> 00:00:45,469 那我们开始呢,可以把这么一个 9 00:00:45,990 --> 00:00:50,745 j指针指向这个结果里面的最小的那个元素, 10 00:00:51,188 --> 00:00:54,951 我们可以依次来处理,来得到第i个 11 00:00:54,951 --> 00:01:00,264 这个元素。那我们首先呢,把当前的这个 12 00:01:00,805 --> 00:01:08,099 结果里面第i个这个元素呢存在 这个临时变量Temp里面。 13 00:01:08,564 --> 00:01:15,699 然后呢,我们把占据了这个下标的第i位的这个元素 14 00:01:16,129 --> 00:01:21,561 和我们真正应该是待在这个第i个这个位置的 15 00:01:21,866 --> 00:01:25,390 这个元素呢我们给它进行一下交换。 16 00:01:26,216 --> 00:01:31,569 同时要注意修改我们这个 17 00:01:31,915 --> 00:01:35,618 已经调整到位的这个 18 00:01:36,024 --> 00:01:39,679 第i位的这个元素,它的next域是 19 00:01:40,794 --> 00:01:46,660 指向它刚才过来的那个j的那个指针。 20 00:01:46,660 --> 00:01:50,887 那也就是说,我们保留了这么一个交换轨迹。 21 00:01:51,654 --> 00:01:56,767 然后,我们现在要处理的这个第j个这个元素呢, 22 00:01:56,767 --> 00:02:01,416 我们又是顺着刚才保留的这个TempRec 23 00:02:01,860 --> 00:02:07,918 它的next域,那我们就是移到了下一位的这样一个待处理的元素。 24 00:02:08,932 --> 00:02:13,513 那如果我们得到的这个j呢,它是小于等于i的, 25 00:02:13,513 --> 00:02:18,813 那表明我们所得到的这个j呢,它其实是 26 00:02:19,271 --> 00:02:23,217 一个轨迹。我们要顺着这个链呢,去找, 27 00:02:23,218 --> 00:02:29,130 找到实际需要处理的那样的一个j 28 00:02:29,129 --> 00:02:37,512 的一个位置。然后我们一直这样的循环进行, 就能够在θ(n)的时间内把这个链整理好。 29 00:02:38,585 --> 00:02:42,589 那结果呢就是按照我们的下标位从小到大排序。 30 00:02:43,525 --> 00:02:49,539 如果我们排序的时候发现这个数据域特别大, 31 00:02:50,120 --> 00:02:51,787 那因为我们排序时间呢主要是由这个记录之间的比较时间 32 00:02:55,935 --> 00:03:01,428 以及我们移动记录了这么移位时间来组成的, 33 00:03:02,250 --> 00:03:09,135 那对于这么大记录的情况呢,如果我们移位很多,那它的时间开销是很大的。 34 00:03:09,803 --> 00:03:13,951 那我们能不能够在前面加一个索引? 35 00:03:14,687 --> 00:03:19,917 那我们发现这个记录需要进行交换或者是赋值的时候呢, 36 00:03:19,917 --> 00:03:26,563 我们是 只对这个索引呢进行,而不整理这个数据域。 37 00:03:27,048 --> 00:03:28,581 那我们排序的结果就保留在这样一个索引数组里面。 38 00:03:32,929 --> 00:03:39,083 那最后呢根据这个索引数组来一次地整理这个数据域。 39 00:03:39,912 --> 00:03:43,631 那我们可以节省排序的整体时间。 40 00:03:44,689 --> 00:03:49,137 那我们来看一下刚才这样的一个 41 00:03:49,137 --> 00:03:53,651 示意的话呢,我们对这样的一个排序的 42 00:03:54,114 --> 00:04:01,650 一串记录,那我们结果呢就放在这么一个索引的数组里头, 43 00:04:03,162 --> 00:04:07,985 那如果我们能够开辟一个新数组, 44 00:04:08,631 --> 00:04:15,725 那我就能够知道,比如说,这个在下标第0位应该是放 45 00:04:16,169 --> 00:04:21,853 现在下标5的这个位置的数据,那我就直接从这边拿过来, 46 00:04:22,441 --> 00:04:26,586 然后我们依次这样处理。那也是在θ(n) 47 00:04:26,586 --> 00:04:31,103 的时间内完成了这个整理。但是它的空间代价是比较大的。 48 00:04:31,478 --> 00:04:37,887 其实我们不必要新开一个空间,那我们后面会给大家介绍一个整理的方法。 49 00:04:39,053 --> 00:04:44,433 那 我们得到的这样一个索引排序的方法,其实 50 00:04:44,434 --> 00:04:49,908 对于我们前面介绍的这些内排序的方法呢,都是适用的。 51 00:04:50,485 --> 00:04:56,788 那我们只需要把那些赋值或者是交换这样的操作呢, 52 00:04:57,395 --> 00:05:03,765 改变成为对我们的索引数组的操作。当然相应的对这些记录的 53 00:05:03,995 --> 00:05:09,741 关键码进行比较的时候呢,也要对这个索引域所指向的 54 00:05:09,742 --> 00:05:14,312 那个相对的这样一个元素的进行比较。 55 00:05:16,271 --> 00:05:21,240 那我们看一下插入排序,我们怎么样对它进行修改, 56 00:05:21,945 --> 00:05:26,690 来变成一个索引地址排序。那首先呢,我们把 57 00:05:27,372 --> 00:05:31,631 这个索引数组呢,都是它的这个下标域, 58 00:05:32,047 --> 00:05:36,049 指向自己,也就是说我自己就待在自己该待的位置。 59 00:05:36,658 --> 00:05:42,427 然后我们可以看,下面是一个插入排序的经典的框架。 60 00:05:42,427 --> 00:05:47,234 那我们当前要处理的是第i个记录, 61 00:05:47,234 --> 00:05:51,818 那我们前面0到i-1呢,它都是已经有序的。 62 00:05:51,818 --> 00:05:57,435 那我们把这个第i个记录要插入到前面一个合适的位置, 63 00:05:57,745 --> 00:06:02,532 那所谓这个合适的位置呢,就是我这个待处理的这 64 00:06:02,532 --> 00:06:07,494 第i个这个元素呢,跟前面这些已排序的元素逐个比。 65 00:06:08,280 --> 00:06:11,700 如果我发现逆置对呢就交换,那一直交换到 66 00:06:11,700 --> 00:06:15,784 某一个元素它跟我当前要处理的这个第i个记录 67 00:06:15,784 --> 00:06:22,861 它是正序对,然后呢,当然前面的那些呢都是逆序对。我们发现正序对,我们就停止。 68 00:06:23,815 --> 00:06:29,453 那 我们注意在这里我们的交换当然是要对 69 00:06:29,452 --> 00:06:35,078 这个索引域里面呢相应的这个元素来进行的, 70 00:06:35,477 --> 00:06:41,485 也就是说我们对索引进行,而不对这个数据域里面那个数据本身进行。 71 00:06:43,133 --> 00:06:47,454 然后我们在比较的时候呢,也是比的相应的 72 00:06:47,454 --> 00:06:52,903 这个索引域所在的那个索引下标它指向的那个数据所在的 73 00:06:53,474 --> 00:06:58,167 那个关键码的值。那我们 74 00:06:58,739 --> 00:07:02,528 比完以后呢,那我们就 75 00:07:03,274 --> 00:07:07,698 会得到这么一个插入排序的一个正确的 76 00:07:08,066 --> 00:07:14,244 它的一个排序结果。但是结果呢,是保留在这个索引域里面。 77 00:07:14,828 --> 00:07:22,795 那我们需要对它进行一个顺链的 一个整理。那我们来看这个整理的过程。 78 00:07:22,794 --> 00:07:29,046 如果我们不再开一个大数组,我们怎么样顺链来进行。 79 00:07:29,047 --> 00:07:32,916 那首先我们在下标0这个位置我们说应该放入 80 00:07:33,251 --> 00:07:37,978 下标5的这个数值。那我先把这个下标0位置 81 00:07:37,978 --> 00:07:42,460 它的这个记录呢先存起来,然后把下标5这个元素给顶过来。 82 00:07:42,885 --> 00:07:47,051 然后呢,下标5的这个位置它要放下标4 83 00:07:47,438 --> 00:07:54,480 位置的这个值。那我们这个34’也顶上来,那相应的34顶上来 84 00:07:55,283 --> 00:07:59,619 然后呢我们在这个下标2这个位置,它说要放下标0这个数值, 85 00:08:00,166 --> 00:08:03,558 那我们这个下标0的这个29呢顶上来。 86 00:08:03,944 --> 00:08:08,185 那因为我们前面已经存在那儿了,那我们就把它拿过来就行了。 87 00:08:08,587 --> 00:08:12,859 那现在呢,它就完成了一个子循环。这个 88 00:08:13,839 --> 00:08:17,515 结果呢,就都分别调整到位。那我 89 00:08:17,515 --> 00:08:22,046 接着呢再去看下一个没有处理的这个元素。 90 00:08:22,046 --> 00:08:24,822 那 91 00:08:24,822 --> 00:08:27,571 这个25呢,它已经待在合适的位置,我们接着 92 00:08:28,215 --> 00:08:33,454 就再看下标3这个位置。那它又是有一轮子循环。 93 00:08:33,991 --> 00:08:36,343 然后我们就给它调整到位了。 94 00:08:38,260 --> 00:08:42,307 那我们来看一下这个整理的一个算法, 95 00:08:42,748 --> 00:08:48,524 首先呢,我们就是按照这个下标0开始到下标n-1, 96 00:08:49,100 --> 00:08:53,525 顺着进行一个单程循环的处理。 97 00:08:53,526 --> 00:08:57,681 那在这里面呢,我们有若干的小循环了。 98 00:08:57,681 --> 00:09:00,456 那我们当前的这个 99 00:09:00,740 --> 00:09:08,414 第i个元素它的下标,我们先给它保留在j里面。 100 00:09:08,414 --> 00:09:12,770 而且把它的这个元素值呢,给它保留在这么一个临时变量里面。 101 00:09:13,592 --> 00:09:20,409 那如果我们这样的一个索引域它所指向的这样一个下标呢, 102 00:09:20,831 --> 00:09:29,592 不等于i的情况, 那这个时候呢我们就把这个相应的 103 00:09:30,182 --> 00:09:34,210 后面我们需要给它填到当前这个 104 00:09:35,952 --> 00:09:40,111 进位的这个数值呢,我给它往前移过来。 105 00:09:40,111 --> 00:09:46,217 而且呢,我们要注意,要相应地修改它的这个索引域的下标。 106 00:09:46,216 --> 00:09:49,314 那 107 00:09:49,314 --> 00:09:53,958 我们这样的一层小循环运行完毕的时候呢,其实就是我们 108 00:09:53,958 --> 00:10:00,122 刚才看到的我回归到索引域的下标等于我们最开始起始的下标的时候。 109 00:10:00,122 --> 00:10:05,114 那这一层小循环就完成。啊,那完成以后呢, 110 00:10:05,114 --> 00:10:11,102 我们这个前面存的那么一个临时的纪录,我 111 00:10:11,102 --> 00:10:13,921 就可以填入了这个,哦, 112 00:10:14,425 --> 00:10:18,403 倒数的那个最后处理的那一个纪录。那, 113 00:10:18,954 --> 00:10:26,013 哦,同时呢,我们要注意把这些下标域呢,也进行相应的修改。 114 00:10:26,384 --> 00:10:33,976 那我们这个循环在下一次进行的时候呢, 我们也是,如果,你这个纪录已经调整到位了, 115 00:10:34,498 --> 00:10:39,923 那你相应的这个下标域呢,它的这个索引值就是自己。 116 00:10:40,477 --> 00:10:45,331 那就不需要处理,所以我们这个循环不会反反复复拉锯地进行。 117 00:10:45,331 --> 00:10:51,198 我们就是一轮扫描过来,已经处理过的它不参加,后面的继续处理。 118 00:10:51,198 --> 00:10:53,392 那我们还有第二种索引方案。 119 00:10:54,047 --> 00:11:00,872 那这个第二种索引方案呢,我们可以看出就是说在这样的一个索引域呢, 120 00:11:01,268 --> 00:11:09,065 是表示的,我这个元素本身应该待在哪一个下标位置。那比如说 121 00:11:09,149 --> 00:11:15,266 29这个元素它因该待在下标2这个位置。我们另外开辟一个数组的话呢, 122 00:11:15,589 --> 00:11:21,541 也是能够单遍地扫瞄,很快地就把这些元素就填充到位。 123 00:11:22,832 --> 00:11:25,355 嗯,但是这个是比较浪费空间的。 124 00:11:25,692 --> 00:11:29,833 那我们,嗯,可以类似于第一种这个方案, 125 00:11:29,832 --> 00:11:34,196 我们也是不需要在另外开辟一个大的数组。 126 00:11:34,542 --> 00:11:38,010 就利用这些索引域来进行整理。 127 00:11:38,505 --> 00:11:43,581 那,嗯,开始的时候我们发现这个,嗯, 128 00:11:44,320 --> 00:11:49,844 29这个元素,哦,那它是应该待在下标域2这个位置。 129 00:11:50,445 --> 00:11:57,565 那我就,嗯,把这个下标域2的这个元素呢,先放到临时变量里面,然后29填过去。 130 00:11:57,979 --> 00:12:05,514 那,这个下标域2的这个位子呢,它说,它自己应该放在下标域4,那我就也往前头挤。 131 00:12:05,987 --> 00:12:09,914 那这也是有一个小的循环,一直 132 00:12:10,462 --> 00:12:15,842 在回到了这个我们开始的这个位置,那我们 133 00:12:15,842 --> 00:12:19,978 这一个数据呢,也是有3组这样的小循环。 134 00:12:20,489 --> 00:12:27,672 那我们依次来处理这些数据呢,那就整理好了。 135 00:12:30,179 --> 00:12:32,486 那最后呢,给大家留几个 136 00:12:32,486 --> 00:12:36,122 思考题。啊,首先呢就是我们证明一下, 137 00:12:37,317 --> 00:12:44,335 前面介绍的这些地址排序的整理方案,它都是在θ(n)的时间可以完成的。 138 00:12:45,662 --> 00:12:49,614 还有呢,我们介绍了说第一种索引的方法, 139 00:12:50,156 --> 00:12:56,244 对于我们前面说过的这些内排序的方案呢,我们都可以试用, 140 00:12:56,577 --> 00:13:01,425 啊,我们只需要对它进行一些小的修改。那我们尝试一下,修改 141 00:13:01,835 --> 00:13:06,251 快速排序,我们在排序的过程中呢,我们不交换 142 00:13:06,665 --> 00:13:11,559 这些数据域而只是对索引进行一些操作。在 143 00:13:11,750 --> 00:13:17,927 排序完成了以后,我们进行一个θ(n)的一个索引整理的过程,然后 144 00:13:17,927 --> 00:13:25,189 得到一个按照我们的下标有序的一个,哦,排好序的一个数组来返回。 145 00:13:26,162 --> 00:13:32,251 那,另外呢就是我们可以查一下这个Rank排序的方法。 146 00:13:32,772 --> 00:13:39,303 我们通过这种方法呢,能够得到第二种索引的这样的一个数组。 147 00:13:40,059 --> 00:13:42,059 嗯,还有呢就是,哦,我们在上一讲介绍的这个静态链的基数排序。 148 00:13:47,796 --> 00:13:52,140 那它的这个结果呢,其实我们可以进行一个特别简单的 149 00:13:52,140 --> 00:13:56,475 一个变换,就得到了我们说的第二种索引的方案。 150 00:13:56,837 --> 00:13:58,139 好,谢谢大家。