归并的思想：
归：就跟分树一样，每次对半分，直到分到1位置
并：从下往上合并,从传入的数组中间分开，左边/右边已经排序好了，此时都从最先结点开始一个一个比大小再合并
要新建一个临时数组
先排序到临时数组再复制回原数组
#include<stdio.h> #include<stdlib.h> void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first; int j = mid + 1; int k = 0; while (i <= mid && j <= last) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= mid) temp[k++] = a[i++]; while (j <= last) temp[k++] = a[j++]; for (i = 0; i < k; i++) //还原回去,从传入first开始还原 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; } int main() { int a[10] = {48,151,13,15,17,18,14,45,46,85}; MergeSort(a,10); for(int i=0;i<10;i++) { printf("%d ",a[i]); } }
