大家好，数据结构与算法。
这一讲的内容，我们对第八章内排序来做一个总结，主要讨论的是
排序算法的时间代价。
我们首先介绍一下这些简单排序它们的时间代价。
然后我们对排序算法进行理论和实验的一些分析比较。
最后呢，我们会来呃说明一下排序问题的下限。
那排序的本质呢，
实际上是对一个随机输入的待排序列。
把它们中间的一些逆序对呢，都给它交换到位。
那所有的逆序对都处理完。
那整个算法呢就处理完毕了。
那对于这些简单的算法来说，
它们的思想主要是对相邻的记录挨个挨个进行处理。
这样的话呢，它们就是低效的方法。
因此它的时间代价总体来说相当于是对我们这个
数组进行了一个双重的循环，它就是θ（n2）的。
那我们来看这几个简单方法它们的时间代价。
平均和最大的情况呢都是θ（n2）的。
那其中直接插入排序， 它在最好的情况下，可以达到θ（n）的。
所以它还是一个很好的算法。而且它具有稳定性。
那在很多一些呃综合的排序应用里面呢，
把直接插入排序作为处理小串的时候的一个函数来调用。
那其他的像冒泡排序呢，它的性能是非常的差的。
虽然说，在最小的情况下，也就是基本有序的时候，它也可以达到θ（n）。
但是它的这个常系数呢是很大的。我们后面可以看到它的实验性能是非常差的。
直接选择排序呢，它在最小的情况下还是
θ（n2）的。因此它也不是很好的算法，而且它还不稳定。
那我们来看呃这几个比较好的排序方法。
那特别是快排、归并排序、堆排，
那它们呢平均情况下是nlogn的。
那嗯对于这个桶排和基数排序来说呢，
呃， 它的时间性能也还是不错的。因为它呃看起来似乎
是呃有一点像线性的，那是跟你这个排序的规模n
有关。然后这个d呢，它似乎是你把它分为几个段，那是就是
d（n+r）。那因为这个r基数比较
小，远远小于n，所以我们看起来是d*n，
而且d很小。但是呢，我们后面可以呃看到呢，这个基数排序
它也并没有本质上好于这种
呃nlogn的排序。它跟它是一个量级的。
那我们这些呃排序方法里面， 可以看到它们的辅助空间来说，呃，
归并排序还有桶排、基数排序，它们用的这个空间是比较大的。
呃基本上是用了跟你的待排数组一样大的一个
辅助空间。然后，桶排和基数排序还需要用到这个桶的空间。
那快排呢，它的辅助空间也不小。虽然看起来它是一个递归实现，我并没有开一个新数组。
但是呢，我们用到了这样的一个变异栈，它也是要占空间的。
而且我们在最坏的情况下，其实应该预留θ（n）的空间。
那logn只是它的一个平均的空间。
呃稳定性来说呢，这几个比较好的算法，呃归并排序，
还有桶排和基数排序是稳定的。其他几个是不稳定的。
那我们对这些算法呢，做一下小结。
呃对于n很小的时候，或者是基本有序的时候，
直接插入排序它是非常好的一个算法。呃也跟其他的一些
呃更优的算法呢，它们会在一些应用情况下综合起来使用。
那Shell排序呢，我们特别要注意要避免
增量除2的递减这样的一个序列。
那我们其实除以3就好很多。
那综合情况下来看呢，快排它确实是一个
最佳的算法，所以它也最著名。我们很多情况下都是用到快排。
我们再来看一下我们的呃测试的一个数据。
那测试环境呢，是这样的硬件和软件环境，这已经是比较旧的了。
那为了这个测试呢，我们首先要产生数据。
那产生数据的话，我们用的是这样的呃随机函数。
而且呢，我们可以产生一个随机数组。那我们可以
根据需要来产生各种不同的随机数组。
那我们再来看，时间测试呢。
我们首先要读这个机器的一个时间，
然后呢，接着我们就运行我们的排序算法。
在排完以后，我再读一次，把这两个时间差呢，
呃那就是作为我们整个这个排序所花的时间。
另外呢，呃我们给出这么一个排序的时间测试框架。
呃也就是刚开始的时候，我们读一下机器时间。
然后呢，我们对这么一个呃
数组呢进行排序。大家可以看到，我其实是 分段来进行的。这个分段的意义呢，
就是对于一些小序列，那我们可能这两个呃
机器时间差啊，可能是已经是0了，你根本得不到数据。
就是你在排序之前读一个时间，排序之后读一个时间，这两个时间差它是0，我看不出差别。
那对这样的情况，我们就要反复测这样的小数据。然后呢，我得到的一个
时间，然后再除以我这个小数据的这个组数，然后得到一个测试的数据。
好，那，
呃，这就是我们的一个测试框架，非常简单。先设置这个呃一个
时间点，然后我们对若干组这样的呃同样规模的数据进行一个排序。
那排完以后呢，我们再读一次这个时间。那我根据我的这个组数呢，
我把这个时间呃来除以这个呃排序的小序列的组数，那就得到
我对这样的规模的小数据，我做这样的一个指定的排序方法所花的时间。
那我们来看这个呃排序的一个实验的结果。
那对于这种规模为10个
待排数据，呃100个，1000个，这样的小规模的情况，其实
就是用到了我们刚才说的这样的方法。
可以从这个结果看到呢，直接插入排序它在小规模的情况下，
它的性能是最好的。在基本有序的情况下，呃
或者是说你看这是一个给的特别的例子就是正序的情况下，
它的性能也是非常好的。因此，它就经常被用于
组合起来做各种这种小规模数据的处理。
那呃在整个这个排序表里面呢，
我们也可以再看一看像这个呃
冒泡排序、选择排序，它们都是比较差的。而且呢，很有意思的就是呃
在正序的情况下，选择排序比冒泡还差。这个冒泡排序
它在发现了这个呃正序的情况呢，它就可以一遍扫描就出来。
然后选择排序呢，它要一次一次再进行，所以选择排序在正序的情况是很差的。
呃但是在一般其他的比较随机的情况下呢，
冒泡排序比这个选择排序都要差很多。当然，
在小规模的情况下，它也比这个直接插入排序要差很多。在Shell排序呢，呃，
增量除以2递减的方法和增量除3 递减的方法
相比，显然是增量除2的那个要差很多。
那呃快速排序它的这个数据是非常好的。呃显然它是一个
呃很好的算法。而且呢，我们对快排进行一些优化，也就是说
当小序列的时候，我们不进行递归，而是
调用这样的直接插入排序来处理。
那它的性能更优。那我们可以看到呢，在我的这一组测试数据里面，呃，
如果对于序列长度小于28的，我不进行递归处理了，我直接调用
这样的直接插入排序，它是达到一个最好的性能。
归并排序也类似，那我们也是对小串呢呃不进行递归的
处理。那我们再重点看一下基数排序的这一些数据。
那可以看到呢，
呃在不同的这个基数下呢，它的性能
是不一样的。那对于我们的这么一个呃64位机的话呢，
我呃对于这样的一个长整数，我处理的时候，我采用呃
基数呃是32的情况，它是得到一个
最好的性能。
呃我们再来分析一下排序问题的
下限。那我们知道，对于一个排序问题，
我需要呃单趟的扫描一遍，
看一下这个数据，这就要花掉一个Ω（n）的时间。
那我们想想，我能不能够达到哎下限是Ω（n）呢？
那其实是呃不行的。那我们首先呢呃知道
它的上限是O（nlogn）。
那我们来看它的下限，在后面我们通过判定树可以发现呢，它的下限
还是Ω（nlogn）。那我们可以
用这么一个判定树来看这么一个排序问题。
那我们呃，一个排序问题的话，如果
对于A,B,C这样的严格不等的三个数据，
我们可能得到的排序结果呢就是以它们的
这种排列的这么一个数目。那，
在我们基于比较的排序方法中呢，那我是可以先拿
A跟B来比，呃有两种情况，就是A<B，或者是B<A。那我分成
两个这样的子节点，再继续去比。
那我再判断这边呢，如果A<B，那我再看A是不是还小于C。
那如果是A<C的话呢， 那我们呃就会得到呃这样的
呃一组可能。呃接着再呃 把B和C呢来进行判断。那我们最后呢，
在叶节点得到了呃我确定的一个结果。
那其他的这些节点的分解呢也类似。
那我们可以看出呢，这个叶节点就是我们刚才说的
这三个数据它们可能的序的情况，
就是呃在所有的叶节点恰好出现。
那因为它是一个呃 排列树，那就是n的阶乘。
那也就是说叶节点正好有n的阶乘个。
那根据二叉树的性质，我们知道这个树的高度啊至少是
log（n！）。那它呢
的一个相应的量级就是nlogn。
那因此我们就知道，在这个判定树里面呢，
它深度最小的情况下，我们最多呢需要呃log（n!）
次比较，那就是Ω（nlogn）。
那因此我们就可以呃得出这么一个结论。在最差情况下呢，
任何基于比较的排序算法呢，它都至少需要Ω（nlogn）的
时间。那也就是说这个下限呢，它是不可能比这个再小。那我们知道上限是
O（nlogn），因此我们可以呃说，
排序问题它的时间代价就是θ（nlogn）的。
那有一个特例， 也就是基数排序。那我们知道它的时间代价呢，
是呃这个我划分成这若干段，
那这个d呢就是段数，然后呢n是待排数据，
r就是我的这个桶的数，那也就是我的这个基数。
那因为r小于小于n，所以我们看起来像是d*n。那d呢，
经常是比较小的数。有的人觉得啊它似乎是个常数。
但实际上它不是一个常数，它还是跟这个n相关的。
我们可以看一下，如果是要表达n个
不相同的关键码，那我的基呢是r。
那要表达这样的不同的数据的情况下呢，我需要
log以r为底、n的对数，这么多位
来表达它。那因此呢，这个d呢它还是在Ω（logn）里面的。
那我们这个呃对于基数排序，它的时间代价
还是nlogn这样的一个量级。它并不是线性的。
最后我们给大家几个思考题。
呃首先呢就是说我们整个内排序
都是在数组的这么一个情况下进行的。那我们是不是
能够用这样的NEW出来这样的指针列表
来实现一些相关的排序算法呢？ 那如果实现了以后，
我们可以看一下性能会有些什么差异呢？另外呢就是，
我们给出了各种排序算法呃它们的稳定性。
那对于这些稳定的算法，你能不能够稍微修改一下，
把它们变成不稳定的。呃当然不能进行大的改动。其实大部分情况下就是对于这种
大于、大于等于这些东西，你可以看一看怎么改，或者是小于、小于等于这些地方。
那还有呢，就是呃
对于那些不稳定的算法，我们是不是可以修改了它呢，使得它变得稳定？那你看
有没有这样的必要把它修改成为稳定。为什么我们一直就是
呃主流的情况下都是就采用那样的不稳定的算法。比如说，
选择排序这样一个非常简单的算法，哎它居然是不稳定的。那我想，
这么简单的我把它弄成稳定的怎么样？但是你可以去看一下背后的算法，
是呃就没有必要的呃复杂。那我们也不采纳这种算法。
还有我们可以调研一下STL里面 这些排序算法啊，
呃这些排序函数呢，它们是怎么组合起来的。你看在什么情况下，
它用到了直接插入排序，什么情况下用到了快排，什么情况下用到了堆排。
那是很有意思的。谢谢大家。