初等排序的复杂度多数为。
高等排序则会涉及，在特定条件下可以达到
(线性时间复杂度)
STL也提供了sort（）函数：
sort（A,A+n,cmp）
接下来将介绍如下排序：
归并排序、快速排序、计数排序。
一些应用：
逆序数、最小成本排序。
Ready Go!
归并排序是基于分治的一种高速排序。
在merge处理中，由于两个待处理的局部数组都已经完成了排序，因此可以采用复杂度为合并算法。
归并排序包含不相邻元素之间的比较，但不会直接交换。在合并两个数组时，如果遇到相同元素，只要保证前半部分数组优先后半数组，相同元素的顺序就不会顺倒。
因此归并排序属于稳定的排序算法。归并排序虽然高效且稳定，但在处理中，需要临时占用一部分内存空间。
利用mergeSort函数将数组不断二分下去：
归并排序的应用：The Number of Inversions(逆序数)
定义:数列中，如果一组数
满足
且
,那么，这组数成为一个逆序，数列A中的逆序的数量称为逆序数。逆序数冒泡算法中的交换次数相等。
显然，不能利用冒泡求逆序数，因为运行一次的话，复杂度为，数据一多出现 Time Limit Exceeded 是大有可能的。
①在每段数组中，分别求逆序数(求的时候其实是在合并的时候)。
②在合并时，若R中比L小的时候，L中本个数开始到最后的数都要算上。
最终的归并逆序数求和函数：
快速排序与归并排序一样基于分治，但在此之前我们要了解分割函数partition()
将数组分为前一段小于某数，后一段大于某数。这里我们选取数列的最后一项。
①分割整个数组为前后两个数组。
②前半部分快排。
③后半部分快排。
快速排序在分割过程中会交换不相邻元素，因此属于不稳定排序算法。
另一方面，快速排序不需要额外的内存空间。也就是说是一种原地排序。
如果快速排序在分割的时候能恰好选择到中间值，则整个过程和归并排序一样被分为层。
快速排序的平均复杂度为是一般情况下最高效的排序方法。
排序方法也是要看数据情况，择优而从。
计数排序是一种稳定的排序方法。考虑到存在多个相等元素的情况下。
*利用数组C记录小于等于A[i]的数在B数组中的具体位置。
只要从输入数组A的末尾开始选择，计数排序就属于稳定排序。
在"非负"的前提下,其运行之间以及内存空间与数组A的最大值成正比。
不过，计数排序能够在线性时间内完成处理，不失高效且稳定的算法。
最小成本排序的过程有点烧脑，公式推导今天再说。（其实是想偷懒了！）
