大家好，数据结构与算法，这一讲的内容，我们学习第八章内排序中，交换排序，包括冒泡和快速排序。
那冒泡和快速排序呢，它们都是基于交换的排序。也就是说， 它们的节点的排序呢，是通过比较这样的逆序对然后完成的交换。
那，我们来看一下，冒泡排序它的思想。
那这个冒泡排序呢，在每一轮呢，它都是从这个 元素的这个最后一个呢，来逐个往前头比，一旦发现逆序对，就相邻地进行交换。
那这样的这个过程中，它每一轮可以交换出当前这些，整体参加运算的元素里面呢，最小的那一个。
然后下一次，缩小规模，还继续这么处理。那一直处理完毕呢，就可以使得整个数组就是排好了序。
那我们有一个有趣的舞蹈，它就是冒泡排序之舞。
那，从这个舞蹈中呢，我们能够看出这些，代表不同的数字的这些演员，他们互相之间，比较了以后，发现逆序对，然后就交换
然后再继续这个过程，每一轮都可以选出最小的那个元素。
那我们来看一下，冒泡排序的这么一个演示。
那我们从最后开始，然后发现逆序对呢，就交换。如果没有逆序对，继续往前推进。
这一轮结束以后，一定选出一个最小。那下一轮呢，也是类似选出次小。
这个冒泡排序的过程，其实我们有一点像
在我们的直接选择排序里面，我们是选出最小，但是呢我们在这个选最小的过程中，我们并没有那么多的交换。
而是直接跟，哦占据着目前的最小位，但它并不一定是最小元素。然后呢，和后面呢，最小位它所在的那个位置，然后我们是 直接的，把它们进行一个大交换.
不在每一个地方进行这样的小的交换。
因此，直接选择排序它在平均的意义下呢， 它是比冒泡排序的效率是更高一些的。
那我们看，冒泡排序的这么一个框架。
那我们在这个外层循环呢，我们的逻辑上是从这个数组的第0位，然后我们一直到它的第n减1位，哦，处理n减1轮，因为最后一轮呢，它只有一个，就不需要处理了。
哦，在每一轮开始处理的时候，我们先做一个标记，就是说这一轮呢，没有进行交换。
如果是这一轮真的进行了交换，那我们就修改一下这个标记。
那在内层的循环呢，我们是从数组的最后这一位开始，然后逐步往前比。
每一次，都是在当前位跟当前位的这个前区那一位呢，进行比较，看看它们是不是逆序对。
如果是，就进行一下交换，而且呢，我们要标记，这个，哦，没交换这个标志位呢，它是假了。也就是说，我们发生了交换，
那，执行完内层这一次的循环，
那如果是说，哦，没有发生交换这个标记，它还是真，
那就说明不需要再进行继续地处理，就可以直接地退出这个冒泡排序
否则呢，如果是有那么一个交换， 那么我们就必须要进入外层循环的下一次继续操作，直到完成排序为止。
冒泡排序这个算法，它是稳定的。
因为在我们排序的过程中，一旦发现逆序对进行交换，它都是跟邻居交换。
那这个邻居呢，是非常缓和的，没有一个大的跨度。
那我们那一些具有重复关键码的这些邻居呢，那如果是说它是等的情况下我们可以不交换，就维持了它的一个相对的次序。
不像在直接选择排序里面呢，它是发现最小，那就跟当前占据的那个最小应该呆的位置的那个元素呢，它俩个进行一个大的交换。
哦，那...那个交换跨越的空间是非常大的，所以直接选择排序它是不稳定的。
哦，空间代价它只有θ(1),
因为我们整个这个排序算法，只在这个swap交换的时候呢，用到了一个临时变量来存这些待交换的数据。
时间代价呢，我们分成比较和交换次数。
比较次数在最好的情况下，就是整个这个数组呢，它是正序的。
那我们在一轮这样的处理的过程中，我们就发现它是正序了，那跟前驱进行比较是不是逆序对。
好，那因此呢，最小情况下就是 θ（n） 的。
那最多的情况下就是它正好是个逆序对的情况
那如果是正好是一个，啊，逆序的这么一个待排序列，那我们每一次处理，一直要处理到整个序列的头部， 然后呢才处理完。
那因此，我们最多的情况下，就会是θ平方这样多的比较次数。
那交换次数呢，也跟刚才的比较，它是相关的。
那，最少的情况下，就是对于一个完全正序的序列，进行这么一次比较，它都是正序的。
所以我们不需要任何的交换，所以最少的时间是0。
那，最多的交换的次数呢，就是完全是一个逆序序列的情况。
我们每次都要交换到头，然后一直是这么做， 那就会是θ(n)平方。
平均起来呢，嗯，我们的交换次数呢，是θ(n)平方的。
那，总的时间代价，我们综合前面的比较和交换，那最大的情况和平均的情况时间代价都是θ(n)平方的。
而最好的情况就是对于完全正序的情况呢，它的时间代价是θ(n)的。
好，那我们再来看一下快速排序另外一种 ，是基于交换的排序方法。
快速排序的思想，它就是先找到一个轴值。这个轴值呢，不一定是在待排序列里面的某一个值。
只要它能够正确地划分这样的一个待排序列就行。
然后我们根据这个轴值把原来的待排序列分成两个子序列，使得这个左边的子序列里面的所有记录都小于或等于轴值。
然后右边呢，都大于轴值。
对于左右这两个子序列，我们又继续进行这样的递归处理，那这就是一个很明显的一个分治的思想。
快排是一个非常重要的算法。
在它提出的时候呢，我们正好是计算机的运用，得到一个迅速的发展。
而排序呢，是像操作系统啊，等等，很多的应用软件里面呢，都广泛地要使用排序的方法。
而快速排序确实是非常的快速高效的。
快速排序，它是一种非常经典的，基于分治的思想。在排序方法里面呢，归并排序也是基于分治的排序。
那我们来看一下，分治的一些策略。
那分治的策略呢，主要就是分，也就是说把大问题划分为小问题
治，就是求解每一个小问题这样的过程。
哦，这些小问题呢，它一定是不能够重叠的。
这样我们才能够分而治之，不要去兼顾其他的什么条件。
最后的合，就是我们把这个前面分治之后的这些结果呢，可能要进行一些收集整理。
那不同的这些呃分治的方法呢，它可能在一些具体的分治合这个过程中，其实处理是不完全一样的。
要根据具体的问题具体分析。
在我们以前接触过的一些算法里面，例如二叉搜索树，还有二分检索，它都是用的分治的思想。
那我们再来看一下这个快排的分治思想。
那首先呢我们找出一个轴值，这个轴值呢它就在这个待排数组里面。然后把它划分为两个子序列。
接着呢，对每一个子序列呢，继续这么处理。
那我们在划分的时候，有可能某一个子序列可能会是空的，那另外一个子序列就是剩下的其他元素。
那我们可以看到快排它在分的过程中，同时就治好了。
因此它分和治是放在一起的。
那这个合的过程在快排里面呢，不是非常的明显。
因为我们每一个轴值，当它自己把这个原来的序列啊分治好之后，它就呆在了最终呆的这个位置。
那我们一直递归地处理到最后那样的只有一个元素或者零个元素的这种子序列的情况呢，它就已经都是处理好了。
我们只要顺序地去看，这个数组里面的元素，它就是有序的。
研究快排的时候，最重要的就是要考虑轴值的选择。
因为它关系到我们分是不是能够分得尽量的均匀。
这是在所有的分治法里面都必须考虑的问题。也就是说我们在划分的时候尽量划分为 ，尽量均匀的子问题。
在选择轴值的时候呢，可能有几种考虑。你可能， 比如说选最右那个元素，或者选最左那个元素。
但是呢这种情况下，对于这种完全正序和完全逆序的输入就会比较糟糕。
如果我们能够随机地选择，也就是使得这个序列呢每次能够真正的比较均匀的分布，当然是比较好的。
实际上，我们有一类这个快速排序的研究呢就是叫做RQS，就是Randomness Quick Sort，就是随机选择。
还有呢，我们可能哎选择这个整个数组里面的这些元素的平均值。
那我反正就是扫一遍，然后计算出它的总和，然后再除以这个数目，就是平均值。
当然其实这个呢也是比较的麻烦，并没有那样的必要。
其实我们就避免那种选最左或者是选最右，最极端情况下造成这样的划分不均匀，就可以了。
那我们来看这个划分的这么一个示例。
那首先我们选32作为轴值，然后呢我们把这个整个数组的最右那个填进去，然后最右这个位置呢就空出来。
空出来，我们从左边开始看。呃这个左边的元素跟轴值来比，看看是不是逆序元素。
如果是逆序元素就表示它不应该呆在左半边，那移到刚才右边腾出的空位。
然后这边呢左边又腾出一个空位，那我们从右边找出一个逆序元素填进去。
那我们一直这么处理。最后找到的这个位置呢就是轴值应该呆的位置。
而我们整个这个划分呢也就完成了。
我们可以看到左边的元素都比轴值小，右边的都比轴值大，轴值呆的位置就是它排序以后应该呆的目标位置，它再也不要动了。
那我们看一下快排的算法框架。
首先呢，我们就是要选这个轴值。
那选完轴值以后呢，我们把这个轴值位所在的这个元素呢跟最右边那个元素呢进行一个交换。也就是说把最右边空出来了。
我们在这里选轴值的算法非常简单，就是整个这个数组里面的最中间的那一个的下标，就做我们轴值那个下标，我给它传进去。
选完轴值以后呢，就进行一个划分。
那这个划分的结果呢呃就是轴值pivot。这个值呢就是我们划分以后轴值的一个正确下标位。
而这里面的整个序列呢，它就在划分的同时被分成了两个子序列。
左子序列比轴值的值要小，右子序列比轴值的值要大。
然后我们把整个这个数组呢分别在它的左半部分和右半部分进行递归的处理。
那我们看分割的这个过程。
我们最开始呢是轴值呢在前面被我们调换到了数组的最右边。然后我们把这个轴值存到Temp这个临时变量里面。
然后我们左右两个下标从两端往中间移动。
如果是说，因为我们现在右边那个位置空出来，所以我们主要就是先从左边找这样的逆序对，就是跟轴值这样的逆序对，就是跟轴值 相比它是逆序的
也就是说它比轴值还要大。
如果找到这样的元素呢，我们就把它填到 右边腾出的那个空位里面。
然后呢右边那个指针呢往前减。
如果它一直是正序的，那我们就是左下标呢接着往右边移，那一直移到 就是左右指针已经颠倒位置了为止。
那这个呢是一个完全对称的过程，跟刚才一样。
那我们最后是在这个左右下标相遇的时候，这个左下标 其实也是右下标，它们所在的这个位置就是轴值应该填入的位置。
而且它的这个下标值呢，就作为轴值的下标传回到上一层。
快速排序它的时间代价呢，是对于n的元素个数的序列。
那我们假设它的代价为Tn。那对于特殊情况我们可以认为是常数的。
然后每一次的分割时间，它都需要对整个数组的元素扫描一遍，所以是cn。
分割以后呢，除了轴值以外，我们分成两个部分。
其实这两个部分的和呢其实是只有n-1个元素了。
然后我们求解这个递推方程。
那我们看最差情况下，那就是一个是空序列，另外一个就是减少一的子序列。
那我们算这个递推方程之后结果就会是θ（n^2）了。
最好情况下就是每一次完全等分。
然后呃等分下来呢，我们算出来它的最好情况下的时间代价就是nlogn。那在平均情况呢，其实就是等概率分布的情况。
而我们认为呢将数组分为0和n-1这样的两个对，1和n-2这样的两个对，那一直这样下来。这些概率呢都是相等的，那都是1/n。
呃我们就可以算T（i）和T（n-1-i）的平均值。
那它们都是呃从0到n-1的求和，就是对T（k）求和的1/n。
那我们把它带进去，带到我们前面的这个公式，
可以得出呢在平均情况下，它的一个时间代价也是nlogn。
那快速排序它最差情的时间代价呢是θ（n2），也就是划分非常不均匀的时候。
那它的空间代价呢θ（n）。那这个空间呢主要就是因为它用到递归。
那我们在一层一层往下面去做的时候呢， 这个栈空间它是需要有这样的支持的。
那最好情况下和平均情况下它的时间代价是nlogn，空间代价是logn。
但是对于这个空间代价我们注意,虽然我们理论上是这样的一个空间代价, 但是对于有些特殊输入可能它也会达到θ（n）这样的空间要求。
因此为了应付这样的极端情况，我们还是要给它准备θ（n）这样的辅助空间，才足够支持快速排序的运算。
最后给大家留几个思考题。
首先呢就是冒泡排序和直接选择排序哪一个方法更优，为什么呢？
快速排序它是不是稳定的，它为什么是不稳定的？
还有快速排序我们能不能够进一步的优化？
例如呢，我们在轴值选择的时候，我们怎么样能够尽量的随机化。
还有就是对于一些小子串的时候，我们不进行递归。
那其实是可以调用一些简单的排序方法，特别是对一些基本有序啊，还有小序列啊， 它的处理效率比较高的这种排序方法。
我们常用的就是插入排序。
还有一个问题就是说 我们怎么样消除整个快速排序里面的递归的这样的框架。
那我们前面学过用栈来消除递归，它显然是可以的。
那在快速排序这样一个算法里面，我们能不能够用队列来消除递归呢？
例如，对这样一个快速排序的分解树，大家想一下，我们怎么样去存储那些将来待处理的这些数据。
然后呢能够很好地支持整个排序的进行。
谢谢大家。