归并排序

归并排序
时间复杂度：O(nlogn)
注意：
1.其他排序算法的空间复杂度是O(1)，而归并排序的空间复杂度很大，为O(n)。
2.下面的end是“末尾索引＋1”，即数列末尾要留一个空位。

首先看图：

归并排序中中两件事情要做：

第一： “分”, 就是将数组尽可能的分，一直分到原子级别。

第二： “并”，将原子级别的数两两合并排序，最后产生结果。

上C++源程序如下：

 1 #include<iostream>
 2 #include <ctime>  //使用了time() 函数 
 3 #include <cstdlib>    //使用了srand()函数 
 4 
 5 const int N=20005;
 6 int a[N];
 7 int temp[N]; 
 8 using namespace std;
 9 
10 void mergesort(int *a, int start, int end)
11 {
12     if (start+1>=end) return;
13     // 划分阶段、递归
14     int mid = start+(end-start)/2;
15     mergesort(a, start, mid);
16     mergesort(a, mid, end);
17 
18     // 将mid两侧的两个有序表合并为一个有序表。
19     int p=start,q=mid,r=start;
20     while (p<mid || q<end)
21         if (q>=end || (p<mid && a[p]<=a[q]))
22             temp[r++]=a[p++];
23         else
24             temp[r++]=a[q++];
25 
26     for (p=start;p<end;p++) a[p]=temp[p];  //临时数组temp的内容赋值给回数组a
27 }
28 
29 
30 
31 int main()
32 {
33     //随机产生n个数存入数组a中 
34     int n=20000;
35     srand(int(time(0)));      //利用时间函数time()，产生每次不同的随机数种子
36     for(int i=1;i<=n;i++) a[i]=rand();  //随机产生3000个数存于数组a中 （从1开始） 
37     clock_t start = clock();
38     mergesort(a,1,n);                   //对数组a进行排序（从1开始） 
39     clock_t end = clock();
40     for(int i=1;i<=20;i++) cout<<a[i]<<' ';    //输出前20个数据（已从小到大排序） 
41     cout<<endl<<"插入排序耗时为："<<end-start<<"ms"<<endl; 
42     return 0;
43 }

在(end-start)不太大时，也可以用插入排序代替归并排序。

由于排序讲得太多，所以希尔排序就不讲了，以后再补吧！