分治思想之归并排序

//将有二个有序数列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++]; else temp[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; }