下面再介绍一个分治算法的例子，快速排序。
快速排序的基本思想呢，用首元素作划分标准。
将输入的数组呢，划分成不超过x的元素构成的一个子数组AL。
它是不超过x的数组，大于x的数呢，构成另外一个数组叫AR。
那么这两个就是两个子问题。
把它存放在数组的左边和右边两半 部分，然后我们递归地对这两个子问题
进行排序，还是用同样的算法来排序，直到子问题的规模
到1的时候，这个是递归停止的条件。下面我们看一下它的伪码
这个伪码呢，它里边是，原始的是
算法它处理的是p到r这样的一个范围。
这里边是产生两个子问题以后，它递归的来处理两个子问题。
这个第一个数组是从p到q的位置 q减1的位置，那么第二个数组是从q加1到r的位置
q的位置呢正好是排好序以后首元素应该放置的那个位置。
那这就是对子问题递归的来处理，这是划分 的过程，通过划分找到首元素放置的正确的位置。
然后把首元素放好，放好以后，那前后两个子问题就产生了。
所以通过这个算法呢，我们把初始的位置定成1。
最后的位置定成n，就对原始规模是n的输入可以调用这个算法来
进行排序。下面看一下这个划分的过程。
划分的过程呢，它是这样做的，从后到前
依次的元素和首元素比较，找到不超过首元素的
这样的元素，找到第一个不超过首元素的元素，从后向前找。
那么后边呢是从前向后找，找比首元素大的元素。
那么找到这样一对元素呢，就进行交换，交换完了以后
从现在的这个位置还继续向里边，两边
都向中间进行搜索，再找第二个可以交换的元素。
直到这两个指针碰到为止，下面我们看一个具体的例子。
这是原始的数组，首元素是27，从后向前找，第一个比它小的25。
从前向后找，第一个比它大的，99。
然后这两个元素进行交换。
交换过去以后，接着从这个位置还向前找
找第二个比首元素小的，然后从这个位置 向后继续找比首元素大的，那么64和10
再进行交换，进行交换以后，再接着找第三
对交换的元素，那就是7和86再交换。
交换完了以后呢，这个时候，从 86再往前找，找到比它小的元素就是16了。
要是从前向后找，再找比它大的元素，结果还是这个86。
这个情况下，16和86已经是相邻的元素，这个前边的指针已经比后边这个
指针的位置还要靠后了，在这个情况下就
找到了首元素应该放置的正确位置，就是这个16的这个位置。
然后把16和27交换，交换以后，首元素放好了，前面的元素都是比首元素小
的或者是可能跟它相等的，后面都是 比首元素大的，这就划成了两个子问题。递归地
对前面这个子问题和后面这个子问题仍旧进行快速排序就可以了。
它的时间复杂度满足 这样的公式，就是说在最坏的情况下
有可能你划到的两个子问题，一个是n减1大小，另外一个
没有，所以你这个情况下，它的工作量达到了最大。
这个是划分过程的工作量，而划到的以后的子问题只比原来小1。
那么它的初值呢是W1等于0，这个 解是2分之n乘n减1，这是最坏情况的比较次数。
那么最好的划分，就是正好这个首元素正好在中间，每次划分都在中间，因此
产生两个子问题呢，都是2分之n规模的，这个是划分过程的工作量，和刚才这个一样。
如果是处在这个情况下，就是每次划分，子问题都是减半的这样减少。
那这个方程的解呢可以得到是nlogn。
这就比这个最坏的情况要好，这是n平方量级，这是nlogn量级。
所以我们看到在 划分正好两个子问题一样大的时候，这个解更好一些。
那有的时候，可能达到一种均衡的划分就是两个子问题大小不一样，但它的比例
永远保持着某个比例，比如说两个子问题大小是1比9的这样一个结果。
那这样划分以后呢，第一个子问题是 10分之n规模，第二个大概10分之9n的规模
就是它是它的9倍，如果每次划分都遵循着这个比例的时候。
那这一项的工作量是划分过程的工作量，应该是iiin量级的工作量。
那如果安装这个方程来解的话，它的结果呢也会是一个比较好的结果，是一个nlogn。
所以不一定非两个子问题一样大，只要保持某个比例的话，它的结果也是nlogn。
那我们看一下刚才那个1比9的那个划分。
那左边这个子问题呢是原来的10分之1。
右边这个子问题呢大概是原来的10分之9，所以你生成的递归数
这个工作量是它的10分之1，这个工作量是它的10分之9，那么这一项又是它的10分之- 1，这一项又是它的10分之9。
这是它的10分之1，这是它的10分之9，所以可以照这样 的生成下去，生成的结果呢我们看一下
每一行加起来，第一行是On，第二行这两个量加起来还是On
第三行还是On，我们可以照这样地加起来。
加起来以后可以得到最终的工作量是nlogn，就是把这些个都加起来。
一共多少层呢？因为你这个每个都是10分之9，10分之9的k次方
它相当于再乘以n的话，最后变到初值1。
可以解一下，这个层数应该是logn量级，所以最后会得到这个结果。
因此我们看到在均衡划分的情况下，这个算法也是nlogn的算法。
下面看一下平均的复杂度，如果首元素排在各个位置的
这个概率都一样，都是n分之1的时候。
那我们看一下，它在，排在位置1，两个子问题大小，前面是
没有元素的0，后面是n减1个元素，排在位置2，前面的
子问题一个元素，后面是n减2的元素，一直到排在位置n减1
和排在位置n，这是它前后两个子问题的 工作量。那么把这些个工作量全部加起来
然后除以n种可能性，除以n，就是平均的复杂度。
那把这些个都加起来，我们发现从T（1）到T（n-1），每个都出现两次。
然后划分的工作量都是n-1。
这样就可以得到这种递推方程。
这个递推方程呢，如果把它整理一下，每个项
从T1到Tn减1，每个项都出现两次会得到这个结果。
然后把这个n减1 它是写到这儿，n减1
写到这儿，然后前面这个n分之1，因为每个出现两项，这个出现一
个n分之2，这就每个都出现两项了，那这个方程的解呢，就是nlogn。
以前我们曾经通过叉消的方法化简了这个方程，并解出了它的解。
关于这个快速排序算法呢 可以做一个小结，它是一个分治的策略。
那么这个策略，和前面讲过的比如说芯片测试啊 还有像我们所讲到的这个
幂乘啊，这些个算法啊，它的分治不太一样。
它的子问题的划分它是通过首元素来决定划分。
通过首元素作为标准，来进行一轮选择。
挑出子问题，所以我们看到这个例子它主要体现到就是我们产生
子问题的方法有很多种规约的方法，这个快速排序呢就是通过首元素
它作为标准来做的挑选，挑选出的元素构成的子问题，
的子问题，最坏情况的算法的复杂度是n平方的算法。
平均情况呢可以达到nlogn的算法，这是 快速排序算法一个典型的分治算法的简单介绍。
Wanling QuProfessor
