首页 > 代码库 > 归并排序

归并排序

学习了冒泡排序,选择排序,归并排序这些常用的排序,我们发现这些排序的时间复杂度都为O(n^2),算法效率十分低下,接下来我们来学习一种复杂度较低的排序,归并排序。

归并排序是基于分治的算法思想,分治法是将一个大问题分解成多个小问题,解决这些规模较小的问题,再将得到的答案合并,从而得到原来的规模较大的问题的答案,俗称 分-治-合

应用在排序方面,即为归并排序。可以试想一下,将一个大的无序序列等分成两个无序序列,对他们各自进行排序,再将排好序的两个有序序列有序的合并成一个大的有序序列,即得到要求的有序序列。

具体步骤:将一个大的序列不断等分,一直到每一个小序列中只有一个元素,这时每个小序列一定是有序的,再将他们不断的有序合并,最终得到要求的有序序列。

代码如下:

 1 void merge(int *p,int *tp, int left, int mid, int right)
 2 {
 3     int i = left,k = left;
 4     int j = mid+1;
 5     while(i <= mid && j <= right)
 6     {
 7         if(p[i]<=p[j])  tp[k++] = p[i++];
 8         else  tp[k++] = p[j++];
 9     }
10     while(i<=mid) tp[k++] = p[i++];
11     while(j<=right) tp[k++] = p[j++];
12     for(i = left; i <= right; i++)
13     p[i] = tp[i];
14 }
15 void mergesort(int *p,int *tp, int left, int right)
16 {   
17      int mid;
18      if(right-left>0) 
19      {
20          mid = (right + left)/2;
21          mergesort(p,tp,left,mid);
22          mergesort(p,tp,mid+1,right);
23          merge(p,tp,left,mid,right);    
24      }
25     
26 }

 归并排序的时间复杂度:长度为n的序列,需要分裂logn次,而后有序合并小序列时,时间是线性的,复杂度为O(n),所以总的时间复杂度为O(nlogn);

eg:归并排序的时间复杂度和冒泡,插入等排序相比,要优秀很多,但是我们在代码中可以看到,在归并排序中在有序合并是需要开设一个同等大小的新的数组,所以归并排序实际是一个牺牲空间去优化时间的算法。

归并排序