[C语言] 归并排序的特性及实现

[C语言] 归并排序的特性及实现

1、算法特性

　　归并排序是一种高效且稳定的排序方法，其速度仅次于快速排序，但比较占用内存。

　　其时间复杂度最好、最差、平均情况均为O（nlog(2)n），空间复杂度为O（n）。

2、算法思路

　　采用分治法的思路将问题分解、细化、逐个解决，即通过递归将无序序列不断分解，直到分解成序列有序（当序列长度为1时一定有序）。再将分解的有序序列不断合并成新的有序序列，最后合并成一个有序序列。

3、实现代码

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 // 归并排序：arr  [left,mid]区间升序  [mid+1,rigth]升序   合并这个数组的数据使之升序
 5 void merge(int arr[],int left,int mid,int rigth)
 6 {
 7     int len = mid-left+1;
 8     int* p = malloc(sizeof(int)*len);
 9     // 把[left,mid-1]区间的数据移动到p指向的内存
10     // memcpy(prr,arr+left,l1*sizeof(int));
11     for(int i=0; i<len; i++)
12     {
13         p[i] = arr[left+i];
14     }
15     // 把p[0,len-1]  arr[mid,rigth]两部分数据合并到 arr[left,rigth]数组里
16     int i = 0;
17     int j = mid+1;
18     int k = left; // 从left开始放
19     while(i<len && j<=rigth)
20     {
21         if(p[i] < arr[j])
22         {
23             arr[k++] = p[i++];    
24         }
25         else
26         {
27             arr[k++] = arr[j++];    
28         }
29     }
30     while(i < len)
31     {
32         arr[k++] = p[i++];    
33     }
34 }
35 
36 // 通铺使arr left-rigth区间有序
37 void _merge_sort(int arr[],int left,int rigth)
38 {
39     if(left >= rigth) // 只有一个数据  那本来就有序
40     {
41         return;
42     }
43     int mid = (left+rigth)/2;
44     // left mid   mid+1 rigth
45     if(mid > left)
46     {
47         _merge_sort(arr,left,mid); // 让数组 [left,mid]有序
48     }
49     if(rigth > mid+1)
50     {
51         _merge_sort(arr,mid+1,rigth); // 让数组  [mid+1,rigth]有序
52     }
53     merge(arr,left,mid,rigth); // 合并
54 }
55 
56 void merge_sort(int arr[],int len)
57 {
58     _merge_sort(arr,0,len-1);
59 }
60 
61 void travel(int arr[],int len)
62 {
63     for(int i=0; i<len; i++)
64     {
65         printf("%d ",arr[i]);    
66     }    
67     printf("
");
68 }
69 
70 int main()
71 {
72     int arr[] = {53,82,9,233,43,14,55,9,4,67};
73     int len = sizeof(arr)/sizeof(arr[0]);
74 
75     travel(arr,len);
76     merge_sort(arr,len);
77     travel(arr,len);
78 
79     return 0;
80 }

4、测试结果