首页 > 代码库 > 归并排序

归并排序

算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。

 1 //将有序数组a[]和b[]合并到c[]中 2 void MemeryArray(int a[], int n, int b[], int m, int c[]) 3 { 4     int i, j, k; 6     i = j = k = 0; 7     while (i < n && j < m)//n,m分别是a,b数组的长度 8     { 9         if (a[i] < b[j])10             c[k++] = a[i++];11         else12             c[k++] = b[j++]; 13     }15     while (i < n)16         c[k++] = a[i++];18     while (j < m)19         c[k++] = b[j++];20 }

以上算法效率可达到O(n)。

来看归并排序:

 归并排序可分为分解,解决,合并三个阶段。

其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了?

可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序。

 1 //将有二个有序数列a[first...mid]和a[mid...last]合并。 2 void mergearray(int a[], int first, int mid, int last, int temp[]) 3 { 4     int i = first, j = mid + 1; 5     int m = mid,   n = last; 6     int k = 0; 7      8     while (i <= m && j <= n) 9     {10         if (a[i] <= a[j])11             temp[k++] = a[i++];12         else13             temp[k++] = a[j++];14     }15     16     while (i <= m)17         temp[k++] = a[i++];18     19     while (j <= n)20         temp[k++] = a[j++];21     22     for (i = 0; i < k; i++)23         a[first + i] = temp[i];24 }25 void mergesort(int a[], int first, int last, int temp[])26 {27     if (first < last)28     {29         int mid = (first + last) / 2;30         mergesort(a, first, mid, temp);    //左边有序31         mergesort(a, mid + 1, last, temp); //右边有序32         mergearray(a, first, mid, last, temp); //再将二个有序数列合并33     }34 }36 bool MergeSort(int a[], int n)37 {38     int *p = new int[n];39     if (p == NULL)40         return false;41     mergesort(a, 0, n - 1, p);42     delete[] p;43     return true;44 }

摘自http://blog.csdn.net/morewindows/article/details/6678165

归并排序