排序：
我们为何要研究排序？
1. 有时候应用程序本身需要对信息进行排序。
2. 许多程序把排序程序作为关键子程序。
3. 排序是我们学习编程的基本的训练，对于程序的优化有很重要的作用。
我们之前已经学过简单排序法和冒泡排序法。接下来我们介绍一下插入排序和合并排序。
1. 插入排序
输入：n个数(a 1 ,a 2 ,.....a n)
输出：输入序列的一个排序(b1,b2....bn),使得b1 <= b2 <=....<=bn
插入排序的机制和打牌时整理手中的牌做法差不多。摸牌的时候，需要将摸到的牌插入到手中一把牌中的正确的位置上。为了要找到这张牌的位置，我们需要将它与手中每张牌从右到左进行比较。无论何时，左手中的牌都是排好序的。
这个算法中，所有的元素都是原地排序（sorted in place），就意味着这些数字就是在数组本身中重新排序的。
算法如下：
1、数组被分为两部分，一部分为排好序的，一部分为未排好序。
2、选取一个key值，就是将要排序的元素，通过比较方式，将其插入到已排好顺序的部分。
3、循环处理，直到该数组全部排好序。
伪代码：
代码（c语言实现）：
//a 是一个数组，size_a是这个数组的元素个数
void insertion_sort( int * a, int size_a){
int i,j;
int key = 0 ;
for (j = 1 ;j < size_a;j ++ ){
key = a[j];
i = j - 1 ;
while (i > = 0 << a[i] > key){
a[i + 1 ] = a[i];
i = i - 1 ;
}
a[i + 1 ] = key;
}
return ;
}
插入排序算法的时间复杂度是O(n 2 ) 。当然算法的执行速度，和n的大小（输入规模）以及样本的结构有关系。考虑坏的情况，就是输入的n个数为逆序排列，此时插入排序算法，随着n的增大，运算时间的增长与 n 2 同数量级。
2.分治法策略
很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的子问题。这些算法通常采用分治策略：将原问题划分为n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治模式在每一层递归上都有三个步骤：
分解（divide）：讲原有问题分解成为一系列子问题；
解决（Conquer）：递归地解各子问题。若子问题足够小，则直接求解；
合并（Combine）：讲子问题的结果合并成原问题的解。
合并排序
合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做合并，引入一个辅助过程merge(a,p,q,r)，其中a是一个数组，p，q和r是下标，满足p <＝ｑ< r。该过程的子数组 a[p...q]和a[q+1.... r] 都已排好序，并将他们合并成一个已排好的子数组代替当前子数组a[p.....r]。
merge过程的代价是O(n)。其中n = r - p + 1是待合并的元素个数。
以下为合并的伪代码：
为了能检查两个子数组是否是空，其想法是在每一个数组底部放一个“哨兵”，它包含了特殊值，用于简化代码。
具体来说，merge过程是这样工作的：第一行计算子数组a[p...q]的长度n1,第二行计算子数组a[q+1...r]的长度n2.在第三行中，创建了数组L和R，长度各位n1 +1,n2 + 1.第四到第五行中的for循环将子数组a[p...q]复制到L[1....n1]中去。 第六到第七行中的for循环将子数组a[q+1...r]复制到R[1....n2]中去。第八九行讲哨兵置于L和R的末尾。第十到第十七行，是合并的具体过程。通过比较，将两子数组按照从小到大的方式合并，存入数组A中。
c语言描述如下所示
void merge( int * a, int p, int q, int r){
int n1 = q - p + 1 ;
int n2 = r - q;
//为左数组和右数组分配空间，为max预留空间。
//max为哨兵，标志数组的结束。
int * L = ( int * )malloc( sizeof ( int ) * (n1 + 1 ));
int * R = ( int * )malloc( sizeof ( int ) * (n2 + 1 ));
for ( int i = 0 ;i < n1;i ++ ){
L[i] = a[p + i];
&nnbsp; }
for ( int i = 0 ;i < n2;i ++ ){
R[i] = a[q + i + 1 ];
}
L[n1] = MAX;
R[n2] = MAX;
//从小到大将左数组和友数组合并。
int i,j,k;
for (i = 0 ,j = 0 ,k = p;k < = r;k ++ ){
if (L[i] < = R[j]){
a[k] = L[i];
i ++ ;
} else {
a[k] = R[j];
j ++ ;
}
}
free(L);
L = NULL;
free(R);
R = NULL;
return ;
}
合并merge过程就可以作为合并排序中的一个子程序来使用。伪代码如下：
c语言描述过程为：
void merge_sort( int * a, int p, int r){
int q = 0 ;
if (p < r){
q= (p + r) / 2 ;
merge_sort(a,p,q);
&nbsnbsp; merge_sort(a,q + 1 ,r);
merge(a,p,q,r);
}
return ;
}
合并程序的具体图示：
关于分治法排序的简要分析：
我们将一个规模为n的问题，拆分成n个规模为1的子问题。拆分的过程经历了
lg n + 1层，在合并时，每一层的问题规模为n，则总代价为O (n * lg n + n ) ，忽略低阶项和常数项，因此合并排序法的时间复杂度为O(n lg n )。
接下来会介绍一下堆排序和快速排序。以上的所有排序方法，都是比较排序。也就是说，他们通过对数组元素比较来实现排序。比较排序法是有极限的，从坏的输入情况，比较排序法的时间复杂度是 O(n lg n )。我们介绍的合并排序以及快速排序，都是渐进优的比较排序方式。我们还会介绍可以突破比较排序极限的排序方式——计数排序。
