1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 #include <vector> 8 #define LL long long 9 #define MAXI 2147483647 10 #define MAXL 9223372036854775807 11 #define eps (1e-8) 12 #define dg(i) cout << "*" << i << endl; 13 using namespace std; 14 15 int a[10]; 16 17 /*L：数组左端下标，R：数组右端下标，M：中间位置下标 18 此函数整合两个数组为一个有序数组，这两个数组分别为{a[l],a[l+1],...,a[m]} 19 和{a[m+1],a[m+2],...,a[r]}.*/ 20 void MergeArray(int L, int R, int M) 21 { 22 vector<int> tmp; 23 vector<int>::iterator it; 24 int l = L, r = R, m = M + 1; 25 //升序排列，故小的元素先压入临时数组 26 //当L<M不成立时，数组{a[l],a[l+1],...,a[m]}已全部压入临时数组 27 //当m<R不成立时，数组{a[m+1],a[m+2],...,a[r]}已全部压入临时数组 28 while(l <= M && m <= R) 29 { 30 if(a[l] < a[m]) 31 tmp.push_back(a[l++]); 32 else 33 tmp.push_back(a[m++]); 34 } 35 //将剩余元素压入临时数组 36 while(l <= M) 37 tmp.push_back(a[l++]); 38 while(m <= R) 39 tmp.push_back(a[m++]); 40 for(it = tmp.begin(); it != tmp.end(); it++) 41 a[L++] = *it; 42 } 43 44 /*L:数组的左端下标，R：数组的右端下标 45 该函数通过递归将数组a不断二分，最终将a拆分为一个个数，每一个数当做一个数组； 46 在回溯时调用函数MergeArray()，从而将单元素数组（即数字）重新合并为有序数组*/ 47 void MergeSort(int L, int R) 48 { 49 int mid = (L + R) / 2; //数组中间位置的下标 50 if(L < R) 51 { 52 /*以下两条语句将数组二分。 53 先处理数组左半段，通过不断地执行语句1将数组左半段拆分为单个数字。 54 在处理完左半段后，再执行语句2以处理数组右半段。第三条语句在二分 55 完成后回溯时执行，作用是合并数字为新的有序数组*/ 56 MergeSort(L, mid); //语句1：处理数组左半段 57 MergeSort(mid + 1, R); //语句2：数组右半段 58 MergeArray(L, R, mid); //语句3：合并数字为新的有序数组 59 } 60 } 61 62 int main() 63 { 64 int i; 65 for(i = 0; i < 10; i++) cin >> a[i]; 66 MergeSort(0, 9); 67 for(i = 0; i < 10; i++) cout << a[i] << " "; 68 cout << endl; 69 return 0; 70 }