首页 > 代码库 > 归并排序
归并排序
注没有排序那一步,在分解的时候你就把它分解成一个个的,相当于排好了序的,所以直接归并就行了
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 void merge(int *a, int p, int q, int r) { 6 int n1 = q - p + 1; 7 int n2 = r - q; 8 int *L = new int[n1]; 9 int *R = new int[n2]; 10 for (int i = 0; i < n1; i++) 11 L[i] = a[p + i]; 12 for (int i = 0; i < n2; i++) 13 R[i] = a[q + 1 + i]; 14 int key = p; 15 int i = 0, j = 0; 16 while (i < n1 || j < n2) { 17 if (i < n1&&j < n2) 18 if (L[i] < R[j]) a[key++] = L[i++]; 19 else a[key++] = R[j++]; 20 else 21 if (i < n1) a[key++] = L[i++]; 22 else a[key++] = R[j++]; 23 } 24 delete[] L; 25 delete[] R; 26 return; 27 } 28 29 void mergeSort(int *a, int l, int r) { 30 if (l < r) { 31 int m = (l + r) / 2; 32 mergeSort(a, l, m); 33 mergeSort(a, m + 1, r); 34 merge(a, l, m, r); 35 } 36 return; 37 } 38 39 40 int main() { 41 int a[100]; 42 int n; 43 while (cin>>n) 44 { 45 for (int i = 0; i < n; i++) 46 cin >> a[i]; 47 48 mergeSort(a, 0, n - 1); 49 50 for (int i = 0; i < n; i++) 51 cout << a[i] << " "; 52 cout << endl; 53 } 54 }
归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。