首页 / 软件开发 / 数据结构与算法 / 经典算法（5） 归并排序的实现

经典算法（5） 归并排序的实现2014-01-03 csdn MoreWindows归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一 个非常典型的应用。

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

//将有序数组a[]和b[]合并到c[]中void MemeryArray（int a[], int n, int b[], int m, int c[]）{int i, j, k;i = j = k = 0;while （i < n && j < m）{if （a[i] < b[j]）c[k++] = a[i++];elsec[k++] = b[j++]; }while （i < n）c[k++] = a[i++];while （j < m）c[k++] = b[j++];}

可以看出合并有序数列的效率是比较高的，可以达到O（n）。

解决了上面的合并有序数列问 题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就 可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

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

//将有二个有序数列a[first...mid]和a[mid...last]合并。void mergearray（int a[], int first, int mid, int last, int temp[]）{int i = first, j = mid + 1;int m = mid, n = last;int k = 0;while （i <= m && j <= n）{if （a[i] <= a[j]）temp[k++] = a[i++];elsetemp[k++] = a[j++];}while （i <= m）temp[k++] = a[i++];while （j <= n）temp[k++] = a[j++];for （i = 0; i < k; i++）a[first + i] = temp[i];}void mergesort（int a[], int first, int last, int temp[]）{if （first < last）{int mid = （first + last） / 2;mergesort（a, first, mid, temp）;//左边有序mergesort（a, mid + 1, last, temp）; //右边有序mergearray（a, first, mid, last, temp）; //再将二个有序数列合并}}bool MergeSort（int a[], int n）{int *p = new int[n];if （p == NULL）return false;mergesort（a, 0, n - 1, p）;delete[] p;return true;}