本文共 1267 字，大约阅读时间需要 4 分钟。
/*因为归并排序至于O（n）的复杂度所以省时*/#include #include #include #include #include #include #include #define N 100010#define MAXN 100010using namespace std;//将有二个有序数列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;}int main(){ //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin); int cur1[]={ 1,4,7,8,5,2,3,6,9,0}; int cur2[12]; mergesort(cur1, 0, 9, cur2); for(int i=0;i<10;i++) cout< <<" "; cout<
转载于:https://www.cnblogs.com/wuwangchuxin0924/p/5866375.html