大家好，数据结构与算法这一讲我们开始第8章，内排序的学习。
首先我们来介绍一下排序的基本概念。
排序呢，就是对一个序列中的记录来进行的一种操作。
序列其实就是我们前面介绍过的线性表。
而表中的元素，在我们这里称为记录。它是排序的基本单位。
在排序问题中，我们很多情况下是针对那种 能够唯一标示这个记录的关键码来进行的。
但是在有一些情况下，我们可能是要对 若干个域，或者是说有重复的这些域,来进行排序。
例如，我们对姓名来排序的话， 可能就有重名的情况。
我们的排序问题呢， 就是根据这个排序码，
我们来对这个序列，进行操作，然后形成一个 不降的这么一个序列，或者是一个不增的一个序列。
整个排序我们如果是规模比较小的情况下，
我们可以认为是在内存完成的。
因为它是线性表 ，所以我们可以看作是在数组里面来进行的。
特别是我们的输入是放在数组里面，输出也放在数组里面。
排序问题我们来给它形式化的看一下。
对于这么一个序列，r 1 到 r n,它对应的 排序码，分别是k 1到k n。
我们排序的目的, 就是形成另外一个有序序列，r1' 到 rn'， 它对应的排序码是变成了k1' 到kn'，
而这个排序码k1'分别是， 有这样的一个性质，
也就是说，这些排序码它会是k1'小于等于k2'， 小于等于，一直到小于等于kn'。
我们这样称为一个不减序。
如果它是严格的小于就不存在等于的情况， 我们可以称为是升序。
相应的，我们可以定义不增序还有降序。
在排序里面， 正序和逆序也是非常重要的概念。
所谓正序就是说你给我的这么一个待排序列， 最好就是你所要求的，这么一个输出的已排好序的序列。
逆序，就是你这个待排序列， 跟你的，要求的这么一个输出结果，它正好是完全颠倒过来了。
还有一个性质就是稳定性，特别是对于有重复排序码的情况。
在排序前和排序后，我们看这些具有重复排序码值的这些记录。
如果它的相对顺序，还是保持不变，例如原来34，34‘， 排完序以后，还是34先出现，34’在后面
这就是一个稳定的排序方法。
如果我们要说明一个算法，它是稳定的， 其实我们应该是进行严格的形式证明。
相应的，就有一种叫做不稳定的排序方法
也就是说，在排序前和排序后， 具有相同的排序码的这些记录，它可能 没有保序，例如我们这一个就是，它颠倒了。
对于不稳定的情况，我们可以举出反例来说明。
排序算法它的衡量的标准，首先是时间代价， 特别是记录的这个比较和移动的次数。
空间代价，主要是指我们为了完成这个排序方法，所需要的辅助空间。
例如，如果我们要对n个元素的数组进行排序。
如果我需要给出一个，同样具有n个这样的元素大小的辅助空间， 它就是O （n）的一个空间代价。
如果我只需要用到一个临时变量来临时的 存放这个大排数组里面的某一个记录，它就是O （1）的空间。
另外还要考虑，算法本身的繁杂程度。 因为排序是在计算机里面反复使用的这么一个基础算法。
也就是说，算法本身它是不是易于编写， 是不是可读，可维护等等，也是非常重要的。
最后，留给大家两个思考问题。
就是排序算法， 它的稳定性有什么意义呢？
我们为什么要考虑正序和逆序的情况呢？谢谢大家。