首页 > 代码库 > 归并排序 堆排序
归并排序 堆排序
1、归并排序
#include "stdafx.h"#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#define maxn 111111using namespace std;int n, a[maxn], b[maxn];void mergesort(int ll, int rr){ if (ll == rr) { b[ll] = a[ll]; return; } mergesort(ll, (ll + rr) / 2); mergesort((ll + rr) / 2 + 1, rr); int p1 = ll, p2 = (ll + rr) / 2 + 1, cnt = ll; while (p1 <= (ll + rr) / 2 && p2 <= rr) { if (b[p1] < b[p2]) { a[cnt++] = b[p1]; p1++; } else { a[cnt++] = b[p2]; p2++; } } while (p1 <= (ll + rr) / 2) { a[cnt++] = b[p1]; p1++; } while (p2 <= rr) { a[cnt++] = b[p2]; p2++; } for (int i = ll; i <= rr; i++) b[i] = a[i]; }int _tmain(int argc, _TCHAR* argv[]){ scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); mergesort(0, n - 1); for (int i = 0; i < n; i++) printf("%d ", b[i]); printf("\n"); return 0;}
2、堆排序
#include "stdafx.h"#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#define maxn 1111111using namespace std;int n, a[maxn];void pushdown(int x){ while (x * 2 +1< n) { int j = 1; if (x*2+2<n && a[x * 2 + 2] < a[x * 2 + 1]) j = 2; if (a[x]>a[x * 2 + j]) swap(a[x], a[x * 2 + j]); else break; x = x * 2 + j; }}int _tmain(int argc, _TCHAR* argv[]){ scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = (n - 1) / 2; i >= 0;i--) pushdown(i); int cnt = n; for (int i = 0; i < cnt; i++) { printf("%d ", a[0]); swap(a[0], a[--n]); pushdown(0); } return 0;}
归并排序 堆排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。