排序算法04之------------------------归并排序

1.归并排序

　　归并排序采用的思想是分而治之，简单来说，就是将一个待排序的序列，不断划分，最终得到有序的序列（只剩一个元素的序列就是有序序列），然后将这些有序的序列进行合并，第一次合并将只有一个元素序列的有序子序列进行合并，就会得到有两个元素序列的有序子序列，然后进行第二次合并，将有两个元素序列的有序序列进行合并，就会得到有四个元素序列的有序序列，如此下去，直到全部元素有序。

举个例子就会一目了然：

待排序序列：1 -9 3 8 6 2 3 -1

第一次划分：1 -9 3 8　　　　6 2 3 -1 得到两个序列

第二次划分：1 -9 　　3 8　　6 2　　3 -1 得到四个序列

第三次划分 ：1　　-9　　3　　8　　6　　2　　3　　-1 得到8个序列，此时每个序列都是有序的，因为只有一个元素

合并

第一次合并：-9 1　　3 8　　2 6　　-1 3　　得到四个有序序列

第二次合并：-9 1 3 8　　-1 2 3 6　　得到两个有序序列

第三次合并：-9  -1 1 2 3 3 6 8　　得到一个有序序列，排序完成。

2.步骤

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个标志，表示两个有序序列的开始位置

第三步：比较两个标志所指向的元素，选择相对小的元素放入到合并空间，并移动标志到下一位置

重复步骤3直到某一个序列元素全部比较完

然后将另一序列剩下的所有元素直接复制到合并序列尾

代码如下：（采用递归）

 1 #include<stdio.h>
 2 void merge(int * arr,int left,int mid,int right)
 3 {
 4     int i=left;//左边子序列的起点 
 5     int j=mid+1;//右边子序列的起点 
 6     int temp[10];//暂时数组 
 7     int n=0;//本次合并元素的个数
 8     
 9     //比较两个序列，将符合要求的元素放进temp数组 
10     while(i<=mid&&mid<=right)
11     {
12         if(arr[i]<arr[j])
13             temp[n++]=arr[i++];
14         else
15             temp[n++]=arr[j++];
16     }
17     //如果左边序列还有剩 
18     while(i<mid)
19         temp[n++]=arr[i++];
20         
21     //如果有边序列还有剩     
22     while(j<=right)
23         temp[n++]=arr[j++];
24         
25     //将排序好的元素放回原本数组对应的位置 
26     for(i=0;i<n;i++)
27         arr[left++]=temp[i];
28 }
29 void mergesort(int * arr,int left,int right)
30 {
31     
32     if(left<right)
33     {    
34         int mid=(left+right)/2;//分治 
35         mergesort(arr,left,mid);//递归左边序列 
36         mergesort(arr,mid+1,right);//递归右边序列 
37         merge(arr,left,mid,right);//开始合并 
38     }
39 
40 }
41 int main()
42 {
43     int i; 
44     int arr[10]={1,3,-9,0,10,2,8,9,19,-1};
45     mergesort(arr,0,9);//归并排序
46     for(i=0;i<10;i++)
47         printf("%d\n",arr[i]);
48     return 0;
49 } 

结果：

 

 归并排序的时间复杂度是：o(nlog₂n)是一种效率很高的算法，并且是稳定的排序算法。稳定是指在排序的时候，相等的元素不会进行交换。