banner
cos

cos

愿热情永存,愿热爱不灭,愿生活无憾
github
tg_channel
bilibili

归并排序循环实现(存用)

递归的归并排序是很占空间和时间的,而非递归算法就不一样了,额外空间复杂度最少为 O (N)。
陈越姥姥的慕课里就讲得很清楚~戳这儿
这里就直接上代码 + 注释了

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int inf  = 0x3f3f3f;
int N;
ll a[maxn];
void swap(ll &a, ll &b){//交换a,b的值
    int tmp = a;
    a = b;
    b = tmp;
}
void Merge(ll a[],ll tmp[], int s, int m, int e) {
    //将数组a的局部a[s,m-1]和a[m,e]合并到数组tmp,并保证tmp有序
    int pb = s;
    int p1 = s, p2 = m;//p1指向前一半p2指向后一半
    while (p1 <= m-1 && p2 <= e) {
        if (a[p1] <= a[p2])
            tmp[pb++] = a[p1++];
        else 
            tmp[pb++] = a[p2++];
    }
    while(p1 <= m-1) 
        tmp[pb++] = a[p1++];
    while(p2 <= e) 
        tmp[pb++] = a[p2++];
    for (int i = 0; i < e-s+1; ++i)
        a[s+i] = tmp[i];
}
void Merge_Pass(ll a[], ll b[], int N, int len) {
    //将a数组按len长度切分 归并到b
    //len为当前有序子列的长度
    int i;
    for(i = 0; i <= N - 2*len; i += 2*len) 
        //找每一对要归并的子序列 直到倒数第二对
        Merge(a, b, i, i+len, i+2*len-1); //将a
    if(i+len < N) //最后有2个子列
        Merge(a, b, i, i+len, N-1);
    else  //最后只剩1个有序子列
        for(int j = i; j < N; ++j) b[j] = a[j];
}
void Merge_Sort(ll a[], int N) {
    int len = 1;//初始化有序子列的长度
    ll *tmp;
    tmp = new ll[N];
    if(tmp != NULL) {
        while(len < N) {
            Merge_Pass(a, tmp, N, len);
            len *= 2;
            Merge_Pass(tmp, a, N, len);
            len *= 2;
        }
        delete [] tmp;
    } else printf("空间不足");
}
int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; ++i) 
        scanf("%lld", &a[i]);
    Merge_Sort(a, N);
    for(int i = 0; i < N; ++i) {
        printf(" %lld"+!i, a[i]);
    }
    return 0;
}

在这里插入图片描述

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。