1 #include <stdafx.h> 2 #include “iostream” 3 #include “time.h” 4 #include “stdlib.h” 5 using namespace std; 6 //合并函数 7 void Merge(int *_Array, int p, int q, int r) {// p:第0个;r:第n-1个数,q:第(r + p) / 2个数 8 int len1 = q - p + 1; 9 int len2 = r - q; 10 int *L = new int[len1 + 1];//用动态数组储存左边的数 11 int *R = new int[len2 + 1];//用动态数组储存右边的数 12 13 for (int i = 0; i < len1; i++) {// 把Array数组左边的数放入L数组 14 L[i] = _Array[p + i]; 15 } 16 17 for (int j = 0; j < len2; j++) {// 把Array数组右边的数放入R数组 18 R[j] = _Array[q + 1 + j]; 19 } 20 L[len1]=R[len2]=INT_MAX; //定义无穷大 21 int i = 0, j = 0; 22 for (int k = p; k <= r; k++) { 23 if (L[i] < R[j]) {//小的放左边，大的放右边 24 _Array[k] = L[i]; 25 i++; 26 } 27 else { 28 _Array[k] = R[j]; 29 j++; 30 } 31 } 32 } 33 // 归并排序 34 void MergeSort(int _Array[], int p, int r) { 35 if (p < r) {//p:第0个;r:第n-1个数。数组至少要有两个数据 36 int q; 37 q = (r + p) / 2;//拆分两组 38 MergeSort(_Array , p , q);//拆分第0个到第 (r + p) / 2个 ，即拆分左半部分 39 MergeSort(_Array , q+1 , r);//拆分第(r + p) / 2个到第r个 ，即拆分右半部分 40 Merge(_Array , p , q , r);//调用合并函数，从第0个到第n-1个排好 41 } 42 } 43 44 int main() { 45 int n; 46 cout << “输入产生的数组个数：”; 47 cin >> n; 48 cout << endl; 49 int *Array = new int[n]; 50 cout << “产生的随机数组为：”; 51 srand((unsigned)time(0)); 52
53 for (int i = 0; i < n; i++) { 54 Array[i] = (rand()%(100-0+1))+0; 55 //cin>>; 56 cout<<Array[i]<<“ ”; 57 } 58 cout<<endl; 59
60 MergeSort(Array,0,n-1); 61
62 cout << “排序后的数组为：”; 63 for(int j = 0;j<n;j++){ 64 cout<<Array[j]<<“ ”; 65 } 66 // int a; 67 // cin>>a; 68 return 0 ; 69 }
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/201612.html