归并排序学习笔记

前言

前段时间学长发了一道关于逆序对处理的题目，没有做出来，痛定思痛还是好好学学归并排序法。

归并排序

归并排序是一种基于分治的排序算法，核心思想是把数组不断拆分为小数组，排好序后再两两合并成更大的有序数组。

基本步骤如下：

分：把数组从中间拆分为左右两个部分
治：递归地对左右两个数组进行归并排序
合：把两个已有序的数组进行合并

合并时用两个指针分别指向两个子数组的开头，每次比较两个指针指向的元素，把较小的放入结果中。

代码实现

这里以结构体排序问题为例，问题描述如下：

第一行输入整数n
第二行开始每行输入工号和工资
根据工资升序输出
输出工资保留两位小数

直接归并排序即可。

#include<stdlib.h>
#include<stdio.h>

typedef struct NODE {
    int id;
    double s;
}NODE;
void merage(NODE a[],int l,int mid,int r) {
    int n1=mid-l+1;
    int n2=r-mid;
    NODE *L=(NODE *)malloc(sizeof(NODE)*n1);
    NODE *R=(NODE *)malloc(sizeof(NODE)*n2);
    for(int i=0;i<n1;i++) L[i]=a[l+i];
    for(int i=0;i<n2;i++) R[i]=a[mid+1+i];
    int i=0,j=0,k=l;
    while(i<n1&&j<n2) {
        if(L[i].s<=R[j].s) {
            a[k++]=L[i++];
        }
        else {
            a[k++]=R[j++];
        }
    }
    while(i<n1) {
        a[k++]=L[i++];
    }
    while(j<n2) {
        a[k++]=R[j++];
    }
    free(L);
    free(R);
}
void merage_sort(NODE a[],int l,int r) {
    if(l<r) {
        int mid=l+((l+r)>>1);
        merage_sort(a,l,mid);
        merage_sort(a,mid+1,r);
        merage(a,l,mid,r);
    }
}
int main() {
    int n;
    scanf("%d",&n);
    NODE *a=(NODE *)malloc(n*sizeof(NODE));
    for(int i=0;i<n;i++) {
        scanf("%d%lf",&a[i].id,&a[i].s);
    }
    merage_sort(a,0,n-1);
    for(int i=0;i<n;i++) {
        printf("%d %.2f\n",a[i].id,a[i].s);
    }
    return 0;
}

实际上，如果不要求使用动态数组的话更好写，直接扔个全局数组就行了。

#include<stdlib.h>
#include<stdio.h>

typedef struct NODE {
    int id;
    double s;
}NODE;
NODE a[1000000],c[1000000];
void merage_sort(int l,int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    merage_sort(l,mid);
    merage_sort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r) {
        if(a[i].s<=a[j].s) {
            c[k++]=a[i++];
        }
        else {
            c[k++]=a[j++];
        }
    }
    while(i<=mid) {
        c[k++]=a[i++];
    }
    while(j<=r) {
        c[k++]=a[j++];
    }
    for(int i=l;i<=r;i++) {
        a[i]=c[i];
    }
}
int main() {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d%lf",&a[i].id,&a[i].s);
    }
    merage_sort(0,n-1);
    for(int i=0;i<n;i++) {
        printf("%d %.2f\n",c[i].id,c[i].s);
    }
    return 0;
}