首页 > 代码库 > 归并排序 堆排序

归并排序 堆排序

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;}

 

归并排序 堆排序