1
00:00:00,000 --> 00:00:04,030
这次课我们主要考虑问题的复杂度。

2
00:00:04,030 --> 00:00:07,840
以排序问题为例来做一些分析。

3
00:00:07,840 --> 00:00:14,280
首先我们看排序算法。现有的一些排序算法，

4
00:00:14,280 --> 00:00:20,720
我们把它列在这里，像插入排序、冒泡排序、快速排序、堆排序、

5
00:00:20,720 --> 00:00:28,090
二分归并排序。这些排序算法它们的特点都是以元素的比较作为基本运算。

6
00:00:28,090 --> 00:00:36,100
这些个算法，它的时间复杂度 有下面的两种复杂度，（有）最坏情况的复杂度，

7
00:00:36,100 --> 00:00:45,900
这个是平均情况的复杂度。对于这些个复杂度，
我们后边会给出它的具体的分析方法是怎么得出来的。

8
00:00:45,900 --> 00:00:50,390
下面我们就对这些算法，先做一个大致地介绍。

9
00:00:50,390 --> 00:00:57,170
首先看到插入排序。插入排序算法呢，是，这是一个输入。

10
00:00:57,170 --> 00:01:06,245
我们假定它是顺序地从后面插入， 插入第二个，认为前两个排好了；再插入第三个，

11
00:01:06,245 --> 00:01:10,650
再认为排好了；再插入第四个，照这样的办法来插入。

12
00:01:10,650 --> 00:01:13,910
我们先看一个插入一个数的过程。

13
00:01:13,910 --> 00:01:23,550
我们假定前边的这五个数都已经排好了。现在插入2，
也就是说，是在这个情况下，来把2插入。

14
00:01:23,550 --> 00:01:31,490
插入的过程呢，是这样做的。先把这个2拿出来，和7比较。

15
00:01:31,490 --> 00:01:37,950
2比7小，7就向后移动；2比6小，6向后移动；

16
00:01:37,950 --> 00:01:44,250
2比5小，5向后移动；2比3小，3向后移动；

17
00:01:44,250 --> 00:01:50,200
2比1大，这个时候，找到了2插入的位置，把2插进来。

18
00:01:50,200 --> 00:01:56,920
这就是一次插入的过程。那么插入以后的结果呢，就变成前面

19
00:01:56,920 --> 00:02:02,210
这几个数都排好了。那下边就可以再插入4。

20
00:02:02,210 --> 00:02:07,700
下面我们看一下，对于这个输入的，它的插入的过程。

21
00:02:07,700 --> 00:02:11,840
一开始，假定5是已经排好的。

22
00:02:11,840 --> 00:02:16,480
下面插入7，接着

23
00:02:16,480 --> 00:02:22,120
插入1，1插到5的前边，下面插入3，

24
00:02:22,120 --> 00:02:31,090
3插在1和5之间， 再插入6，6插在5的后面，7的前面，

25
00:02:31,090 --> 00:02:35,170
再插入2，2插在第二个位置。

26
00:02:35,170 --> 00:02:43,530
最后插入4，到插入4的时候， 所有的数都按照从小到大的顺序排好了，

27
00:02:43,530 --> 00:02:46,940
这是插入排序的算法的运行过程。

28
00:02:46,940 --> 00:02:53,070
下边我们看看冒泡排序。冒泡排序它的基本的过程是

29
00:02:53,070 --> 00:03:01,990
巡回。所谓巡回，就是 从前到后，相邻的两个元素顺序的比较。

30
00:03:01,990 --> 00:03:07,670
如果前边到后边小，出现逆序的时候，他们就做交换。

31
00:03:07,670 --> 00:03:15,560
这样的一个过程，从前走到后就叫做一次巡回。下边我们看一下巡回操作。

32
00:03:15,560 --> 00:03:22,350
对这个初始的数组进行一次巡回。

33
00:03:22,350 --> 00:03:26,580
5和1比较，5和1交换，5比1大。

34
00:03:26,580 --> 00:03:34,270
5和6比较，不用交换。6和2比较，6比2大，进行交换。

35
00:03:34,270 --> 00:03:40,930
6和8不用交换，8和3比较，8交换到后面。

36
00:03:40,930 --> 00:03:44,360
8和4比较， 8交换到后面。

37
00:03:44,360 --> 00:03:48,290
8和7比较， 8交换到后面。

38
00:03:48,290 --> 00:03:53,455
这个就是一次巡回的结果。巡回到最后，我们发现

39
00:03:53,455 --> 00:03:58,620
这个最大数8被放到了它的最后面的位置。

40
00:03:58,620 --> 00:04:04,780
这个就是一次巡回的结果。那这是巡回后的情况。

41
00:04:04,780 --> 00:04:13,210
8放好了位置，前边这些数做了部分的 交换，和初始的（数组顺序）也有的变化。

42
00:04:13,210 --> 00:04:19,060
这就是一次巡回。冒泡排序是通过一次又一次的巡回

43
00:04:19,060 --> 00:04:24,600
来做这个排序工作。下面我们来看这个数组的冒泡排序过程。

44
00:04:24,600 --> 00:04:33,400
第一次巡回 结果就是8到了最后，然后前边做了部分的交换。

45
00:04:33,400 --> 00:04:40,640
那么这个位置是什么呢？是刚才发生交换的位置，是前后两个数发生交换的位置。

46
00:04:40,640 --> 00:04:47,910
这是最后一次发生交换的位置。在这个位置以后的元素，说明已经换好了。

47
00:04:47,910 --> 00:04:54,010
所以下一次巡回的时候，我们只要巡回到最后发生交换的位置就可以了。

48
00:04:54,010 --> 00:05:03,690
接着进行第二个巡回，第二个巡回呢，巡回的结果 是数组变成这个样子。6和7也放好了。

49
00:05:03,690 --> 00:05:06,970
最后一次交换是发生在4和6之间。

50
00:05:06,970 --> 00:05:12,605
那么，第三次巡回只要巡回到这个位置就可以了。第三次巡回以后，

51
00:05:12,605 --> 00:05:18,240
这个4又，4和5都放到了正确的位置。

52
00:05:18,240 --> 00:05:21,720
最后一次交换就是发生在4和5之间。

53
00:05:21,720 --> 00:05:27,580
接着第四次巡回，这个时候3就放到了它的正确的位置。

54
00:05:27,580 --> 00:05:33,425
最后一次交换发生在3和2之间，

55
00:05:33,425 --> 00:05:39,270
下边（是）第五次巡回，对于这个数组进行巡回的时候，没有发生交换。

56
00:05:39,270 --> 00:05:45,320
那么当这个巡回不发生交换的时候意味着所有的数都排好了。

57
00:05:45,320 --> 00:05:52,200
这个算法就可以输出了。下面一个是快速排序算法。

58
00:05:52,200 --> 00:05:58,830
快速排序算法呢，它的做法是把首元素作为一个划分的标准，

59
00:05:58,830 --> 00:06:06,430
从后边向前找第一个比首元素小的（元素），从前边向后边找第一个比首元素大的（元素）。

60
00:06:06,430 --> 00:06:12,790
找到了这样的一对元素以后，进行交换。下边我们看一下它的整个过程。

61
00:06:12,790 --> 00:06:22,770
那么第一次，在做这样的寻找的时候，
找到的是后边这个元素是4，比5小的第一个元素。前边的

62
00:06:22,770 --> 00:06:27,620
第一个比5大的是8，那么这两个元素就发生交换。

63
00:06:27,620 --> 00:06:36,355
发生交换以后接着再从刚才8的位置 向前找，再找第二个比5小的，

64
00:06:36,355 --> 00:06:40,810
从4向后的位置，向后找，再找第一个比5大的。

65
00:06:40,810 --> 00:06:46,440
找的第二个数是个6和2。它们再进行交换，

66
00:06:46,440 --> 00:06:53,800
这次交换呢，是发生在两个相邻的数之间做的。所以可见这个位置

67
00:06:53,800 --> 00:06:59,750
向后的都是比首元素大的，这个位置向前的都是比首元素小的。

68
00:06:59,750 --> 00:07:06,580
那么这个（的）2这个位置，就是首元素在排好序的时候应该放的正确的位置，

69
00:07:06,580 --> 00:07:10,650
因此我们把2和首元素进行交换，

70
00:07:10,650 --> 00:07:17,625
交换以后，就以首元素对这个数组做了划分，划分成两个子问题。

71
00:07:17,625 --> 00:07:24,600
前边这部分都是比首元素小的，后面这部分都是比首元素大的。

72
00:07:24,600 --> 00:07:32,260
这个时候我们就可以对两个子问题，递归地再用快速排序的算法对两个子问题排序。

73
00:07:32,260 --> 00:07:36,490
这样不断地递归调用，就把整个数组排好了。

74
00:07:36,490 --> 00:07:41,580
下面一个排序算法是二分归并排序。

75
00:07:41,580 --> 00:07:48,440
这个排序算法呢，它是从中间，先把这个数组划分开，化成两个子问题。

76
00:07:48,440 --> 00:07:57,650
化成这两个子问题以后，对左边和右边 这两个子问题，同样地用二分归并排序算法进行排序。

77
00:07:57,650 --> 00:08:02,610
那就是说子问题排好了，后边这个子问题也排好了。

78
00:08:02,610 --> 00:08:09,020
然后，最后，把这个两个已经排好的子数组合并起来。

79
00:08:09,020 --> 00:08:16,940
我们看一下这个合并过程。合并过程是从它的首元素和这个首元素进行比较。

80
00:08:16,940 --> 00:08:23,430
哪一个小就把哪一个拿走。那我们看到1和2比，1小，把1拿走。

81
00:08:23,430 --> 00:08:26,610
那下面的首元素是2和3，

82
00:08:26,610 --> 00:08:33,450
2和3比，2小，就把2拿走。3和4比，应该把3拿走。

83
00:08:33,450 --> 00:08:43,450
4和5比，把4拿走。5和6比， 把5拿走。6和8比，把6拿走。

84
00:08:43,450 --> 00:08:49,530
7和8比，把7拿走。最后一个数组空了，

85
00:08:49,530 --> 00:08:54,140
就把剩下另一个数组的元素全部接在后面就可以了。

86
00:08:54,140 --> 00:08:57,500
这就是合并以后的结果。

87
00:08:57,500 --> 00:09:01,710
这个是二分归并排序的一个运行过程。

88
00:09:01,710 --> 00:09:10,900
下面我们看一下，刚才给出了若干个排序算法， 像插入排序、冒泡排序、快速排序、

89
00:09:10,900 --> 00:09:15,360
二分归并排序。堆排序，我们以后会碰到它。

90
00:09:15,360 --> 00:09:22,090
那么这些个算法，前边这一些算法，它的时间是n平方量级的，

91
00:09:22,090 --> 00:09:27,080
而后边这些个算法，它是nlogn量级的。

92
00:09:27,080 --> 00:09:32,380
我们关心的是排序问题还有没有更好的算法。

93
00:09:32,380 --> 00:09:36,995
就是更好的算法是不是存在的。

94
00:09:36,995 --> 00:09:46,295
那么，这里边还有没有更好的算法？哪个算法的效率最高？
就是在所有排序算法里面，甚至包括到现在还没有设计出来（的算法），

95
00:09:46,295 --> 00:09:50,980
也许过两年还会有人提出来更好的排序算法。

96
00:09:50,980 --> 00:09:55,850
把这些算法都考虑在内，哪个算法的效率最高？

97
00:09:55,850 --> 00:10:01,280
那这个问题考虑的是什么问题呢？考虑的排序问题到底有多难？

98
00:10:01,280 --> 00:10:08,090
求解排序问题的最好的算法，它的时间应该到达一个什么样的复杂度。

99
00:10:08,090 --> 00:10:15,100
这是我们所关心的事情。那这个问题呢，它是关于问题计算复杂度的问题，

100
00:10:15,100 --> 00:10:22,660
它不再涉及一个算法。而是求解同一个问题的，千千万万的算法，在一起来考虑的事情。

101
00:10:22,660 --> 00:10:29,080
那这一讲的内容呢，主要介绍了几种简单的排序算法。

102
00:10:29,080 --> 00:10:36,970
接着我们就介绍了排序问题的难度估计。

103
00:10:36,970 --> 00:10:42,340
到底什么是最好的排序算法，这个应该怎么界定，

104
00:10:42,340 --> 00:10:48,000
这件事情也是算法涉及和分析中所要关注的一个重要问题。