1 00:00:04,900 --> 00:00:06,440 大家好。 2 00:00:06,440 --> 00:00:15,860 数据结构与算法这一讲的内容是第八章内排序中 选择排序,包括直接选择排序和堆排序。 3 00:00:15,860 --> 00:00:23,220 那直接选择排序呢,它就是依次选出这个待排序列里面的最小记录。 4 00:00:23,220 --> 00:00:27,920 堆排序它是利用了最大堆来实现的。 5 00:00:27,920 --> 00:00:32,040 那我们看一下直接选择排序的一个演示。 6 00:00:32,040 --> 00:00:37,120 在这个待排的数组里面,我们看到12是最小的。 7 00:00:37,120 --> 00:00:41,220 那我们就把它放到最小的那个位置。 8 00:00:41,220 --> 00:00:49,300 然后接着看到29是最小的,那么我们跟当前占据着最小位置的34进行交换。 9 00:00:49,300 --> 00:01:01,360 那我们依次这样的处理,呃直到我们整个数组的所有元素都被处理完成。那这个排序呢也就完成了。 10 00:01:02,240 --> 00:01:08,020 直接选择排序的这个框架呢是这样一个结构。 11 00:01:08,020 --> 00:01:22,900 首先呢我们, 这每一个待选择的这个位置 ,它所在的那个元素的下标,我们先存到这个smallest里面 12 00:01:22,900 --> 00:01:29,560 也就是说假设我当前看到的这个位置呢它就是具有一个最小值。 13 00:01:29,560 --> 00:01:39,920 然后,我们从这个元素之后一直到呃n之前呢,呃依次地往后面看。 14 00:01:39,920 --> 00:01:49,920 那比较这个后面的这些元素跟我们前面记录下来的这个smallest那个下标位置的元素。 15 00:01:49,920 --> 00:02:03,860 那如果 找到一个比记录的smallest元素更小的,那我们就修改这个 当前看到的最小的这个下标的这个位置。 16 00:02:03,860 --> 00:02:16,560 那在这一轮循环完成以后呢,我们就已经知道在这个待排的这个子序列里面最小的那一个下标是谁。 17 00:02:16,560 --> 00:02:25,180 那我们呃跟i那个下标所在的这个位置它的元素呢互相交换。 18 00:02:25,180 --> 00:02:31,420 那对这个循环呢,我们是操作n-1次。 19 00:02:31,420 --> 00:02:42,920 那也就是说我们依次地选出了第一小,第二小,然后呃最后是第n-1个这样大小的元素。 20 00:02:42,920 --> 00:02:47,040 剩下的最后一个呢,它自然是最大的那一个。 21 00:02:47,040 --> 00:02:52,020 那我们整个这个算法呢,它是不稳定的。 22 00:02:52,020 --> 00:02:57,220 主要的就是我们在选择第i小的时候, 23 00:02:57,220 --> 00:03:07,800 那我们会是找到这个后面待排子序列里面的那个具有第i小的这样的一个元素 24 00:03:07,800 --> 00:03:13,540 跟我们当前占据着这个元素下标i的这个元素呢进行一个交换。 25 00:03:13,540 --> 00:03:17,900 这个交换的跨度非常的大。 所以导致它不稳定。 26 00:03:17,900 --> 00:03:20,880 那它的空间代价呢是θ(1)。 27 00:03:20,880 --> 00:03:32,820 这个主要是我们为了交换这两个元素的时候用的那个swap,它要用到一个临时变量来保存这些数值,来进行交换。 28 00:03:32,820 --> 00:03:37,840 那时间代价呢,我们最主要的是花在比较次数。 29 00:03:37,840 --> 00:03:44,700 我们每一次要在这个待处理的子序列里面依次去查找。 30 00:03:44,700 --> 00:03:51,520 那这双重循环直接下来就是n2的这样的比较次数。 31 00:03:51,820 --> 00:03:57,960 它的交换次数呢,可以说在这些排序算法里面呢都不算多的。 32 00:03:58,120 --> 00:04:05,340 那也就是说,我们发现了这样的一个啊逆序对的情况。 33 00:04:05,340 --> 00:04:17,640 其实这个逆序对指的是我们找到这个第i小,然后在当前这个占据着第i位的这个呢它是并不是第i小的情况,我们需要一个交换。 34 00:04:17,640 --> 00:04:24,080 那恩这个交换次数呢,总共只需要发生n-1次。 35 00:04:24,080 --> 00:04:28,680 那我们总的时间代价呢是θ(n2)的。 36 00:04:29,780 --> 00:04:34,680 堆排序呢,它是利用了最大堆。 37 00:04:34,680 --> 00:04:41,880 那因为最大堆呢,它保留了这些元素的一个相对大小的信息。 38 00:04:41,880 --> 00:04:49,160 那我们找出最大值以后,立马能够找出次大值啊。然后依次找下去。 39 00:04:49,160 --> 00:04:56,760 因此呢,它比我们前面的这样的简单的直接排序方法呢就会要快一些。 40 00:04:56,760 --> 00:05:04,260 还有一些其他的这种选择排序,我们在外排序里面会介绍到。 41 00:05:04,840 --> 00:05:08,920 那我们看一下最大堆的这么一个排序过程。 42 00:05:08,920 --> 00:05:18,820 首先我们建了这么一个最大堆。那它建堆的过程呢是一个线性的,也就是说θ(n)就可以完成。 43 00:05:18,820 --> 00:05:24,380 那找到这个最大值以后呢,我们把它从堆里面删除。 44 00:05:24,380 --> 00:05:32,480 那这个删除呢,实际上是找到这个堆里面的最后这个元素,跟这个堆顶呢进行交换。 45 00:05:32,480 --> 00:05:37,020 那交换完了以后,这个最大值呢,我们就出堆了。 46 00:05:37,020 --> 00:05:39,740 那这个堆的规模缩小1。 47 00:05:39,740 --> 00:05:49,480 然后呢,这个剩余的这些元素啊,我们要从根开始再进行调整。 48 00:05:49,480 --> 00:05:55,900 把它调整成为一个新的规模小1的一个最大堆。 49 00:05:55,900 --> 00:06:04,720 那我们看到这个调整的过程呢,其实我们是找到了这个根它所需要呆的这个位置。 50 00:06:04,940 --> 00:06:14,160 然后呢,我们把这个从根到这个位置上头相应的这些元素呢 都往根的方向上推。 51 00:06:15,120 --> 00:06:20,680 那我们看一下堆排序的这样一个过程。首先我们是建最大堆。 52 00:06:20,680 --> 00:06:24,180 然后呢,我们操作n-1次。 53 00:06:24,180 --> 00:06:30,440 每次呢,都删除这个当前序列里面的最大的那个元素。 54 00:06:30,440 --> 00:06:40,440 那这个最大元素删除完了以后呢,它都是呆在这个数组里面的我们当前的那个相应的位置。 55 00:06:40,440 --> 00:06:44,880 那最大的那个就呆在数组的倒数第一个。 56 00:06:44,880 --> 00:06:47,780 然后,次大的那个呆在倒数第二个。 57 00:06:47,780 --> 00:06:58,120 那我们依次地处理。处理完成以后,正好我们这个数组的元素呢它就是有序的,并不需要额外的整理过程。 58 00:07:00,060 --> 00:07:05,040 堆排序呢,它的建堆过程是θ(n)的。 59 00:07:05,040 --> 00:07:09,960 那我们删除堆顶呢,如果堆里面有n个元素,它就是logn的。 60 00:07:09,960 --> 00:07:13,160 如果是i个元素呢,应该是logi的。 61 00:07:13,160 --> 00:07:23,460 那我们整个这个排序的过程是一次建堆,然后有啊n-1次删除堆顶的操作。 62 00:07:23,460 --> 00:07:29,000 那我们总的时间代价呢是n logn的。 63 00:07:29,000 --> 00:07:39,100 空间代价主要是用在我们进行这个元素的交换或者是移动的时候,那种辅助的空间。 64 00:07:39,100 --> 00:07:43,160 那这个辅助空间的代价是θ(1)的。 65 00:07:43,160 --> 00:07:46,520 最后留几个思考。 66 00:07:46,520 --> 00:07:54,040 首先呢就是直接选择排序那么一个简单的排序方法,它为什么是不稳定的? 67 00:07:54,040 --> 00:07:58,780 我们有没有办法修改它,使得它变成稳定? 68 00:07:58,780 --> 00:08:04,800 另外呢,就是我们对于堆排序算法。我们可以改写它一下。 69 00:08:04,800 --> 00:08:08,660 发现逆序对的时候呢,我们是直接进行交换 70 00:08:08,660 --> 00:08:12,740 而不是说一直要找到它所呆的这个位置 71 00:08:12,740 --> 00:08:25,460 然后再把这个从根顶到我们这样的一个实际位置的这样一个路径上头的这些元素呢逐个往根的方向上推。 72 00:08:25,460 --> 00:08:28,660 谢谢大家。