复杂度
最坏时间复杂度
最好时间复杂度
空间复杂度
1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 void merge1(int a[], int p, int m, int q) 5 { 6 int c = m - p + 1; 7 int b = q - m; 8 //int L[c + 1], R[b + 1]; 9 //int *L = new int[c + 1]; 10 //int *R = new int[b + 1]; 11 vector<int> L(c + 1); 12 vector<int> R(b + 1); 13 for (int i = 0; i < c; i++) 14 { 15 L[i] = a[p + i]; 16 } 17 for (int i = 0; i < b; i++) 18 { 19 R[i] = a[m + i + 1]; 20 } 21 L[c] = INT_MAX; 22 R[b] = INT_MAX; 23 int i ,j; 24 i = j = 0; 25 for (int k = p; k <= q; k++) 26 { 27 if (L[i] < R[j]) 28 { 29 a[k] = L[i]; 30 i++; 31 } 32 else 33 if (L[i] >= R[j]) 34 { 35 a[k] = R[j]; 36 j++; 37 } 38 } 39 } 40 void recursive_mergesort(int a[], int p, int q) 41 { 42 if (p < q) 43 { 44 int m = (q + p) / 2; 45 recursive_mergesort(a, p, m); 46 recursive_mergesort(a, m + 1, q); 47 merge1(a, p, m, q); 48 } 49 } 50 int main() 51 { 52 int a[] = { 1, 5, 6, 88, 8, 99, 88, 0, 1 }; 53 for (auto s : a) 54 cout << s << " "; 55 cout << endl; 56 recursive_mergesort(a, 0, 8); 57 for (auto s : a) 58 cout << s << " "; 59 system("pause"); 60 return 0; 61 }