首页 > 代码库 > 归并排序
归并排序
#include <iostream>using namespace std;void merge(int a[], int p, int q, int r){ int n1 = q - p + 1; int n2 = r - q; int* L = new int[n1 + 2]; int* R = new int[n2 + 2]; L[n1+1]=0x7fffffff; R[n2+1]=0x7fffffff; //复制数组 for(int i = 1; i <= n1; i++) L[i] = a[p + i - 1]; //复制数组 for(int i = 1; i <= n2; i++) R[i] = a[q + i]; int i = 1; int j = 1; //合并 for(int k = p; k <= r; k++) { if(L[i] <= R[j]) { a[k] = L[i]; i++; } else { a[k] = R[j]; j++; } }}void mergesort(int a[], int p, int r){ if(p < r) { int q = (p + r) / 2; mergesort(a, p, q); mergesort(a, q + 1, r); merge(a, p, q, r); }}int main(){ /* * 归并排序 *将一个问题的模n分解成n/2个子问题 *将子问题n分解成n/2个子问题 *最小子问题的模等于1 *初始化: *保持: *终止: */ int a[] = { 0, 8, 6, 7, 1, 5, 4, 2, 3 }; mergesort(a, 1, 8); for(int i = 1; i <= 8; i++) cout << a[i] << " "; cout << endl; return 0;}
归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。