数据结构与算法复习（三）归并排序

归并排序的思想是：将两个有序的子序列通过归并得到一个大的子序列实现序列有序化
算法实现过程如下：
1、将数组划分为一个个最小的子序列，即每个子序列只有一个元素
2、将最小的子序列两两归并得到大的子序列
3、递归执行步骤2，直到归并得到最大的序列，即有序的整个序列

比如如下序列：
16 9 8 20 7 9 6 5
先将序列递归划分成最小的子序列
16 9 8 20 | 7 9 6 5
16 9 | 8 20 | 7 9 | 6 5
16 | 9 | 8 | 20 | 7 | 9 | 6 | 5
将子序列依次归并得到最终有序序列，比如序列16 | 9归并后为9 16
9 16 | 8 20 | 7 9 | 5 6
8 9 16 20 | 5 6 7 9
5 6 7 8 9 9 16 20

归并排序是一种稳定的排序算法。
空间复杂度：归并排序需要一个与原序列等长的空间作为归并时的缓存用，所以空间复杂度为O(n)；

时间复杂度：归并排序的时间主要花费在归并操作上，因为是对有序的子序列归并，只需要扫描一遍子序列元素，
因此一次归并操作花费的时间是O(n)，归并排序将序列划分成log2n种子序列长度不同的序列，因此需要归并操作
log2n次，所以时间复杂度是O(nlog2n)，但是每次归并完成后，需要将归并后的元素拷贝回原序列，因此通常
花费的时间会比快速排序多。

针对已经有序的排序，归并排序可以在归并时对比两子序列的最小元素和最大元素，如果已经有序，则跳过归并
过程，这样时间复杂度就为O(n)

算法代码实现如下：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 /* 用时间做种子产生随机数 */
 5 #include <time.h>
 6 
 7 #define MAXLEN 50
 8 static int tmp[MAXLEN];
 9 
10 void ms(int A[], int left, int right)
11 {
12     /*
13      * left是数组左下标
14      * right是数组右下标
15      */
16     int mid, l, r, k;
17 
18     if (A == NULL || left >= right) {
19         return;
20     }
21 
22     mid = (left + right) / 2;
23     ms(A, left, mid);
24     ms(A, mid + 1, right);
25 
26     l = left;
27     r = mid + 1;
28     k = 0;
29     while (l <= mid && r <= right) {
30         if (A[l] <= A[r]) {
31             tmp[k++] = A[l++];
32         }
33         else {
34             tmp[k++] = A[r++];
35         }
36     }
37 
38     while (l <= mid) {
39         tmp[k++] = A[l++];
40     }
41 
42     while (r <= right) {
43         tmp[k++] = A[r++];
44     }
45 
46     /* 将有序的tmp拷贝到数组A中 */
47     k = 0;
48     for (l = left; l <= right; l++) {
49         A[l] = tmp[k++];
50     }
51 
52 }
53 
54 static void printA(int A[], int len)
55 {
56     int i;
57 
58     for (i = 0; i < len; i++) {
59         printf("%d ", A[i]);
60     }
61     printf("
");
62 }
63 
64 int main(int argc, char **argv){
65     int i, res, len;
66     int A[50]; // = {-1,6,2,3,9,19};
67 
68     srand((int)time(NULL));
69     len = rand() % 51; //51;
70     printf("len is %d.
", len);
71 
72     srand((int)(time(NULL) + len));
73     for (i = 0; i < len; i++) {
74         A[i] = rand() % 100;
75     }
76 
77     printf("before sort :
");
78     printA(A, len);
79 
80     ms(A, 0, len - 1);
81 
82     printf("after sort :
");
83     printA(A, len);
84 
85     return 0;
86 }

数据结构与算法复习（三）归并排序

相关推荐