快速排序的原理
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-Conquer Method)。
该方法的基本思想是： 1．先从数列中取出一个数作为基准数。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。 虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：
先来看实例吧，定义下面再给出（最好能用自己的话来总结定义，这样对实现代码会有帮助）。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
以一个数组作为示例，取区间第一个数为基准数。
1. 如图（1），初始时，i = 0; j = 9; X = a[i] = 72
由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 88 | 85 |
2. 数组变为：如图（2）
i = 3; j = 7; X=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 48 | 6 | 57 | 42 | 60 | 72 | 83 | 73 | 88 | 85 |
3. 数组变为：如图（3）
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
以上是挖坑法，下面讲解“交换法”
int i = l - 1, j = r + 1, x = q[l + r >> 1]; // 这里选的是左端点
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
该循环结束后，出现两种情况:
第一：i == j
这种情况是出现在基准值位置，而且是端点的位置。
第二：j < i
那么就会有两种分法：
一种是按i的，[l, i-1] 和 [i, r]
二种是按j的，[l, j] 和 [j+1, r]
到底选哪一种，要看基准值选的是左端点 (q[l] 或 q[l+r>>1] )还是右端点 (q[r] 或 q[l+r+1>>1] )。
如果是左端点，那么就要用 j 来划分
如果是右端点，那么就要用 i 来划分
7
8 10 2 3 6 1 5
递归过程：
8 10 2 3 6 1 5
[1 3 2 ] [10 6 8 5 ]
/ \
[1 2 ][3 ] [5 6 ][8 10 ]
/ / \
[1 ][2 ] [5 ][6 ] [8 ][10 ]
j>i [5 1 2 3 6 ][10 8 ]
j>i [3 1 2 ][5 6 ]
j>i [2 1 ][3 ]
j>i [1 ][2 ]
i==j [5 ][6 ]
j>i [8 ][10 ]
快速排序性能分析
快排也是用递归来实现的，如果每次分区操作，都能正好把数组分成大小接近的两个小区，那快排的时间复杂度和归并排序相同，也是$O(nlogn)$。
在用递归树推导之前，我们先来加快一下用递推公式的分析方法，你可以回想一直，当时，我们为什么说用递推公式来求解平均时间复杂度非常复杂？
快速排序在最好情况下，每次分区都能一分为二，这个时候用递推公式 $T(n) = 2T(n/2) + n$，很容易就能推导出时间复杂度是$O(nlogn)$。但是，我们并不可能每次分区都这么幸运，正好一分为二。
我们假设平均情况下，每次分区之后，两个分区的大小比例为 $1：k$。当 $k =9$ 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 $T(n) = T(n/10) + T(9n/10) + n$。
这个公式可以推导出时间复杂度，但是推导过程非常复杂。那我们来看看，用递归树来快速排序的平均情况时间复杂度，是不是比较简单呢？
我们还是取 $k$ 等于$9$，也就是说，每次分区很不平均，一个分区是另一个分区的$9$ 倍。如果我们把递归分解的过程画成递归树，就是下面这个样子：
快速排序的过程上，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍历的数据的个数之和就是$n$。我们现在只要求出递归的高度h，这个快排过程遍历的个数就是 $hn$ ,也就是说，时间复杂度就是$O(hn)$。
因为每次分区不是均匀地一分为二，所以递归树不是满二叉树。这样一个递归树的高度是多少呢？
我们知道，快速排序结束的条件就是待排序的小区间，大小为$1$，也就是说叶子节点的数据规模是$1$。从根节点n 到叶子节点$1$，递归树中最短的一个路径是每次都乘以 $1/10$，最长的路径是每次都乘以$9/10$。
所以，根据复杂度大$O$表示法，对数复杂度的底数不管是多少，我们统一写成$logn$，所有当大小比例是$1：9$时，快速排序的时间复杂度仍然是$O(nlogn)$。当 $k = 99$时，算出的时间复杂度也一样。
如果在极端情况下，每次分区，两个小区的大小差别都很悬殊，那么它的时间复杂度会退化为$O(n^2)$。
输入：
1 2 3 4 5 6 7 8 9 10
递归过程：
[1 ][2 3 4 5 6 7 8 9 10 ]
[2 ][3 4 5 6 7 8 9 10 ]
[3 ][4 5 6 7 8 9 10 ]
[4 ][5 6 7 8 9 10 ]
[5 ][6 7 8 9 10 ]
[6 ][7 8 9 10 ]
[7 ][8 9 10 ]
[8 ][9 10 ]
[9 ][10 ]
归并排序性能分析
第一、归并排序是稳定的排序算法吗？
结合代码，在merge()函数中，决断条件是a[before] <= a[after]，当等值时，原本在前面的元素合并后，还是在前面，所以它是稳定的排序算法
第二、归并排序的时间复杂度是多少?
方法一：利用递推公式推导复杂度
如果我们定义求解问题 a 的时间是T(a)，求解问题b、c 的时间分别是T(b)和T(c)，那可以得到这样的递推关系式；
T(a) = T(b) + T(c) + k
其中k等于将问题 b、c 合并成问题a 的结果所消耗的时间。
（不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式）
套用前面的公式，归并排序时间复杂度的计算公式就是：
T(1) = C; n = 1 时，只需要常量级的执行时间，所以表示为 C
T(n) = 2*T(n/2) + n; n>1
// 写的直观一点
T(n) = 2*T(n/2) + n
= 2*( 2*T(n/4) + n/2 ) + n = 4*T(n/4) +2*n
= 4*( 2*T(n/8)+ n/4) +2*n = 8*T(n/8) + 3*n
......
=2^k *T(n/2^k) + k*n
......
$T(n/2^k)=T(1)$
得 $n/2^k = 1$,代入可得 $T(n) = T(n)=Cn+nlog_2n$。即用大O标记法表示，T(n) 是 O(nlogn)。所以归并排序的时间复杂度是O(nlogn)。
归并排序与原始数据的有序度无关，其时间复杂度很稳定，最好、最坏、平均情况复杂度都是$O(nlogn)$。
方法二：递归树分析时间复杂度
归并算法，它的递归代码非常简洁。现在我们就借助归并排序来看看，如何用递归树，来分析递归代码的时间复杂度。
归并排序的原理我就不详细介绍了，它每次会将数据规则一分为二。我们把归并排序画成递归树，就是下面的样子：
因为每次分解都是一分为二，所有代价很低，我们把时间上消耗记叙常量1。归并算法中比较四季风的是归并操作，也就是把两个子数组合并为大数组。从图中我们可以看出，每一层归并操作消耗时间总和是一样的，跟要排序的数据的数据规模无关。我们把每一层归并操作消耗的时间记作 n 。
现在，我们只需要知道这棵树的高度h，用高度h 乘以每一层的时间消耗n，就可以得到总的时间复杂度O(n*h)。
可以看出来，归并排序是一棵满二叉树，那h = log2n ,所以归并排序的时间复杂度就是O(nlogn)。我这里的时间复杂度都是估算的，对树的高度的计算也没有那么精确，但是这并不影响复杂度的计算结果。
举例：T(n) = T(n/2) + O(1) 和 T(n)=T(n-1)+n 如何推导 T 函数 ，我们可以使用不断展开的方法进行推导：
T(n) = T(n/2) + O(1)
= T(n/4) + O(1) + O(1)
= T(n/8) + O(1) * 3
= T(n/16) + O(1) * 4
...
= T(1) + O(1) * logn
= O(logn)
第三、归并排序的空间复杂度是多少？
归并排序不是原地算法，它有一个临时数组，需要额外申请空间，临时数组长度与原数组长度一样，所以空间复杂度是$O(n)$。
接下来，我们来看看归并排序和快速排序，都是分治思想，递推公式也很相似，那区别在哪里呢？
可以看出，归并排序是自下而上的，而快速排序是自上而下的，快速排序通过巧妙的原地分区，实现了原地排序，尽管它不是稳定算法。
总结
归并排序和快速排序，是两种稍复杂的排序算法，它们用的都是分治的思想。代码都通过递归来实现，过程非常相似。重点是是理解，它们的原理。 归并排序算法，任何情况下时间复杂度都是 $O(nlogn)$，但它不是原地排序算法，空间复杂度高$O(n)$，这是它的致命缺点。正因为如此，它没有快速排序应用广泛。 快速排序算法虽然在最坏情况下时间复杂度是 $O(n^2)$。但最好情况，平均情况时间复杂度都是$O(nlogn)$。 而且，快速排序算法时间复杂度退化为 $ O(n^2)$ 的概率非常小，我们可以通过合理地选择基准值（左端，右端，中间值，随机值）来避免这种情况。
例如：遇到原则上有序的数组，先给它随机打乱下 random_shuffle()，再进行排序。
#include<bits/stdc++.h>
using namespace std;
int a[] = {0,0,0,1,1,2,2,2,3,4};
int main(){
srand(time(0)); //初始化随机数种子
random_shuffle(a,a+10);
for(int i=0; i<10; i++){
cout << a[i] << ' ' ;
}
return 0;
}
逆序对
上述提到归并排序是稳定的排序，相等的元索的顺序不会改变，进而用其可以解决逆序对的问题。首先我们了解一下什么是逆序对。
逆序对:设 A为一个有n个数字的有序集(n>1),其中所有数字各不相同。如果存在正整数i,j使得1≤i A[j].则这个有序对称为A的一个逆序对，也称作逆序数。
例如，数组(3,1,4,5,2)的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。
所谓逆序对的问题，即对给定的数组序列,求其逆序对的数量。
从逆序对定义上分析，逆序对就是数列中任意两个数满足大的在前,小的在后的组合。如果将这些逆序对都调整成顺序(小的在前，大的在后),那么整个数列就变得有序，即排序。因面，容易想到冒泡排序的机制正好是利用消除逆序来实现排序的，也就是说，交换相邻两个逆序数，最终实现整个序列有序，那么交换的次数即为逆序对的数量。
冒泡排序可以解决逆序对问题，但是由于冒泡排序本身效率不高，时间复杂度为O(n^2),对于n比较大的情况就没用武之地了。我们可以这样认为，冒泡排序求逆序对效率之所以低，是因为其在统计逆序对数量的时候是一对一对统计的，而对于范围为n的序列，逆序对数量最大可以是(n+1)*n/2,因此其效率太低.那怎样可以一下子统计多个，而不是一个一个累加呢?这个时候，归并排序就可以帮我们来解决这个问题。 在合并操作中，我们假设左右两个区间元素为：
左边：{3 4 7 9} 右边：{1 5 8 10}
那么合并操作的第一步就是比较3和1,然后将1取出来放到辅助数组中,这个时候我们发现，右边的区间如果是当前比较的较小值，那么其会与左边剩余的数字产生逆序关系，也就是说1和3、4、7、9都产生了逆序关系，我们可以一下子统计出有4对逆序对。接下来3,4取下来放到辅助数组后，5与左边剩下的7、9产生了逆序关系，我们可以统计出2对。依此类推,8与9产生1对,那么总共有4+2+1对。这样统计的效率就会大大提高，便可较好地解决逆序对问题。
而在算法的实现中，我们只需略微修改原有归并排序,当右边序列的元素为较小值时，就统计其产生的逆序对数量，即可完成逆序对的统计。
在归并的“并”的过程中，从最小单位1开始，逐步扩大范围，每次合并区间时统计，并逐步消除该区间内的逆序对，然后扩大范围，而每个范围只会处理一次，所以总共的逆序对就可以统计出来。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
