总时间限制: 2000ms 单个测试点时间限制: 500ms 内存限制: 65536kB

描述

随机输入一组数，使用归并排序得到从小到大的序列。

输入

第1行是元素的个数，第2行是各个元素的值，每个元素以空格分隔。

输出

输出有1行，即排完序后由小到大的序列，每个元素之间以空格分隔。

样例输入1

  1. 5
  2. 9 7 8 5 3

样例输出1

  1. 3 5 7 8 9

样例输入2

  1. 10
  2. 9 8 7 6 5 4 3 2 1 6

样例输出2

  1. 1 2 3 4 5 6 6 7 8 9

思路

这个分治要借助递归思想：

  • 递归形式： 把数组分成两半，对每一半再来一次归并排序
  • 递归边界：当元素只剩一个时，停止递归
  • 合并：把上一次数组按从小到大的顺序抄到新数组里

例题-归并排序 - 图1

代码

  1. // Using C99 standard
  2. #include <stdio.h>
  4. void MergeSort(int*, int, int, int*);
  5. void Merge(int*, int, int, int, int*);
  7. int main() {
  9.     int number;
  10.     scanf("%d", &number);
  11.     int array[number], tmp[number];
  12.     for(int i = 0; i < number; i++) {
  13.         scanf("%d", &array[i]);
  14.     }
  16.     MergeSort(array, 0, number - 1, tmp);
  18.     for(int i = 0; i < number; i++) {
  19.         printf("%d ", array[i]);
  20.     }
  21.     printf("\n");
  23.     return 0;
  24. }
  27. void Merge
  28. (int a[], int start, int middle, int end, int tmp[]) {
  29.     int pb = 0;
  30.     int p1 = start, p2 = middle + 1;
  31.     while( p1 <= middle && p2 <= end) {
  32.         if( a[p1] < a[p2] )
  33.             tmp[pb++] = a[p1++];
  34.         else 
  35.             tmp[pb++] = a[p2++];
  36.     }
  38.     while( p1 <= middle )
  39.         tmp[pb++] = a[p1++];
  40.     while( p2 <= end )
  41.         tmp[pb++] = a[p2++];
  43.     /* Copy back to a[] */
  44.     for(int i = 0; i < end-start+1; i++) 
  45.         a[start+i] = tmp[i];
  46. }
  48. void MergeSort(int a[], int start, int end, int tmp[]) {
  49.     if( start < end ) {
  50.         int middle = start + (end - start)/2;   // same as (start + end)/2, in case of overflow
  51.         MergeSort(a, start, middle, tmp);
  52.         MergeSort(a, middle+1, end, tmp);
  53.         Merge(a, start, middle, end, tmp);
  54.     }
  55. }