这次课我们主要考虑问题的复杂度。
以排序问题为例来做一些分析。
首先我们看排序算法。现有的一些排序算法，
我们把它列在这里，像插入排序、冒泡排序、快速排序、堆排序、
二分归并排序。这些排序算法它们的特点都是以元素的比较作为基本运算。
这些个算法，它的时间复杂度 有下面的两种复杂度，（有）最坏情况的复杂度，
这个是平均情况的复杂度。对于这些个复杂度， 我们后边会给出它的具体的分析方法是怎么得出来的。
下面我们就对这些算法，先做一个大致地介绍。
首先看到插入排序。插入排序算法呢，是，这是一个输入。
我们假定它是顺序地从后面插入， 插入第二个，认为前两个排好了；再插入第三个，
再认为排好了；再插入第四个，照这样的办法来插入。
我们先看一个插入一个数的过程。
我们假定前边的这五个数都已经排好了。现在插入2， 也就是说，是在这个情况下，来把2插入。
插入的过程呢，是这样做的。先把这个2拿出来，和7比较。
2比7小，7就向后移动；2比6小，6向后移动；
2比5小，5向后移动；2比3小，3向后移动；
2比1大，这个时候，找到了2插入的位置，把2插进来。
这就是一次插入的过程。那么插入以后的结果呢，就变成前面
这几个数都排好了。那下边就可以再插入4。
下面我们看一下，对于这个输入的，它的插入的过程。
一开始，假定5是已经排好的。
下面插入7，接着
插入1，1插到5的前边，下面插入3，
3插在1和5之间， 再插入6，6插在5的后面，7的前面，
再插入2，2插在第二个位置。
最后插入4，到插入4的时候， 所有的数都按照从小到大的顺序排好了，
这是插入排序的算法的运行过程。
下边我们看看冒泡排序。冒泡排序它的基本的过程是
巡回。所谓巡回，就是 从前到后，相邻的两个元素顺序的比较。
如果前边到后边小，出现逆序的时候，他们就做交换。
这样的一个过程，从前走到后就叫做一次巡回。下边我们看一下巡回操作。
对这个初始的数组进行一次巡回。
5和1比较，5和1交换，5比1大。
5和6比较，不用交换。6和2比较，6比2大，进行交换。
6和8不用交换，8和3比较，8交换到后面。
8和4比较， 8交换到后面。
8和7比较， 8交换到后面。
这个就是一次巡回的结果。巡回到最后，我们发现
这个最大数8被放到了它的最后面的位置。
这个就是一次巡回的结果。那这是巡回后的情况。
8放好了位置，前边这些数做了部分的 交换，和初始的（数组顺序）也有的变化。
这就是一次巡回。冒泡排序是通过一次又一次的巡回
来做这个排序工作。下面我们来看这个数组的冒泡排序过程。
第一次巡回 结果就是8到了最后，然后前边做了部分的交换。
那么这个位置是什么呢？是刚才发生交换的位置，是前后两个数发生交换的位置。
这是最后一次发生交换的位置。在这个位置以后的元素，说明已经换好了。
所以下一次巡回的时候，我们只要巡回到最后发生交换的位置就可以了。
接着进行第二个巡回，第二个巡回呢，巡回的结果 是数组变成这个样子。6和7也放好了。
最后一次交换是发生在4和6之间。
那么，第三次巡回只要巡回到这个位置就可以了。第三次巡回以后，
这个4又，4和5都放到了正确的位置。
最后一次交换就是发生在4和5之间。
接着第四次巡回，这个时候3就放到了它的正确的位置。
最后一次交换发生在3和2之间，
下边（是）第五次巡回，对于这个数组进行巡回的时候，没有发生交换。
那么当这个巡回不发生交换的时候意味着所有的数都排好了。
这个算法就可以输出了。下面一个是快速排序算法。
快速排序算法呢，它的做法是把首元素作为一个划分的标准，
从后边向前找第一个比首元素小的（元素），从前边向后边找第一个比首元素大的（元素）。
找到了这样的一对元素以后，进行交换。下边我们看一下它的整个过程。
那么第一次，在做这样的寻找的时候， 找到的是后边这个元素是4，比5小的第一个元素。前边的
第一个比5大的是8，那么这两个元素就发生交换。
发生交换以后接着再从刚才8的位置 向前找，再找第二个比5小的，
从4向后的位置，向后找，再找第一个比5大的。
找的第二个数是个6和2。它们再进行交换，
这次交换呢，是发生在两个相邻的数之间做的。所以可见这个位置
向后的都是比首元素大的，这个位置向前的都是比首元素小的。
那么这个（的）2这个位置，就是首元素在排好序的时候应该放的正确的位置，
因此我们把2和首元素进行交换，
交换以后，就以首元素对这个数组做了划分，划分成两个子问题。
前边这部分都是比首元素小的，后面这部分都是比首元素大的。
这个时候我们就可以对两个子问题，递归地再用快速排序的算法对两个子问题排序。
这样不断地递归调用，就把整个数组排好了。
下面一个排序算法是二分归并排序。
这个排序算法呢，它是从中间，先把这个数组划分开，化成两个子问题。
化成这两个子问题以后，对左边和右边 这两个子问题，同样地用二分归并排序算法进行排序。
那就是说子问题排好了，后边这个子问题也排好了。
然后，最后，把这个两个已经排好的子数组合并起来。
我们看一下这个合并过程。合并过程是从它的首元素和这个首元素进行比较。
哪一个小就把哪一个拿走。那我们看到1和2比，1小，把1拿走。
那下面的首元素是2和3，
2和3比，2小，就把2拿走。3和4比，应该把3拿走。
4和5比，把4拿走。5和6比， 把5拿走。6和8比，把6拿走。
7和8比，把7拿走。最后一个数组空了，
就把剩下另一个数组的元素全部接在后面就可以了。
这就是合并以后的结果。
这个是二分归并排序的一个运行过程。
下面我们看一下，刚才给出了若干个排序算法， 像插入排序、冒泡排序、快速排序、
二分归并排序。堆排序，我们以后会碰到它。
那么这些个算法，前边这一些算法，它的时间是n平方量级的，
而后边这些个算法，它是nlogn量级的。
我们关心的是排序问题还有没有更好的算法。
就是更好的算法是不是存在的。
那么，这里边还有没有更好的算法？哪个算法的效率最高？ 就是在所有排序算法里面，甚至包括到现在还没有设计出来（的算法），
也许过两年还会有人提出来更好的排序算法。
把这些算法都考虑在内，哪个算法的效率最高？
那这个问题考虑的是什么问题呢？考虑的排序问题到底有多难？
求解排序问题的最好的算法，它的时间应该到达一个什么样的复杂度。
这是我们所关心的事情。那这个问题呢，它是关于问题计算复杂度的问题，
它不再涉及一个算法。而是求解同一个问题的，千千万万的算法，在一起来考虑的事情。
那这一讲的内容呢，主要介绍了几种简单的排序算法。
接着我们就介绍了排序问题的难度估计。
到底什么是最好的排序算法，这个应该怎么界定，
这件事情也是算法涉及和分析中所要关注的一个重要问题。