归并排序

/* 归并排序 划分问题：把序列分成元素个数尽量相等的两半 递归求解：把两半元素分别排序 合并问题：把两个有序表合并成一个 */ #include <iostream> using namespace std; void Merge (int *A, int low, int mid, int high, int *B) //表A的两段A[low...mid]和A[mid+1...high]，各自有序，将他们合并成一个有序表。 { int i, j, k; i = low; j = mid + 1; k = 0; while (i <= mid && j <= high) { if (A[i] <= A[j]) //比较B中左右两段中的元素 { B[k++] = A[i++]; //将较小值复制到A中 } else { B[k++] = A[j++]; } } while (i <= mid) B[k++] = A[i++]; while (j <= high) B[k++] = A[j++]; for (i = 0; i < k; i++) A[low + i] = B[i]; } void MergeSort (int *A, int low, int high, int *B) { if (low < high) { int mid = (low + high) / 2; //从中间划分两个子序列 MergeSort (A, low, mid, B); //对左序列进行递归排序 MergeSort (A, mid + 1, high, B); //对右序列进行递归排序 Merge (A, low, mid, high, B); //合并 } } int main() { cout << "要给几个数字排序："; int num; cin >> num; int * a = new int [num]; int * p = new int [num]; for (int i = 0; i < num; i++) { cin >> a[i]; } MergeSort (a, 0, num - 1, p); for (int i = 0; i < num; i++) { cout << a[i] << ' '; } cout << endl; delete []a; delete []p; return 0; }