题解 P1271 【【深基9.例1】选举学生会】

CSP_SAKME · 2024-10-26 13:59:29 · 题解

这里我们使用手写归并排序 (Merge Sort)。

Part 1 什么是归并排序？

归并排序是一种高效的、基于比较的排序算法，它采用了分治法的思想。归并排序的主要思路是将数组分成越来越小的子数组，直到每个子数组只包含一个元素（此时子数组已经是有序的），然后再将这些有序的子数组逐步合并，最终得到一个完整的、有序的数组。\ 例如：

Part 2 分裂 (拆分)

将待排序的数组从中间分成两半，形成两个子数组。如果数组的长度是奇数，则分割点可以是中间元素的左边或右边，这通常不会影响最终的排序结果。\ 注意！如果只剩一个数，则不需要分裂，直接结束。

if(l==r){//只剩一个数，则不需要分裂，直接结束。
    return;
}
int mid=(l+r)>>1;//等价于(l+r)/2
merge_sort(l,mid);//两边分别排序
merge_sort(mid+1,r);

Part 3 合并

将两个有序的子数组合并成一个有序的数组。这通常是通过比较两个子数组的元素，并将较小的元素依次放入新的数组中来实现的。合并过程需要额外的空间来存储合并后的结果。

int b[r-l+1],k=1;//需要额外的空间来存储合并后的结果
int i=l,j=mid+1;//末尾元素
while(i<=mid&&j<=r){//没有超出边界
        if(a[i]<a[j]) b[k++]=a[i++];//把小的放进去
        else b[k++]=a[j++];
}
while(i<=mid) b[k++]=a[i++];//可能会有多余的，补上
while(j<=r) b[k++]=a[j++];
for(i=l;i<=r;i++){//放回去
      a[i]=b[i-l+1];
}

Part 4 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int a[maxn],www;//www是摆设
int n;
void merge_sort(int l,int r){
      if(l==r){//只剩一个数，则不需要分裂，直接结束。
        return;
    }
    int mid=(l+r)>>1;//等价于(l+r)/2
    merge_sort(l,mid);//两边分别排序
    merge_sort(mid+1,r);
    int b[r-l+1],k=1;//需要额外的空间来存储合并后的结果
    int i=l,j=mid+1;//末尾元素
    while(i<=mid&&j<=r){//没有超出边界
            if(a[i]<a[j]) b[k++]=a[i++];//把小的放进去
            else b[k++]=a[j++];
    }
    while(i<=mid) b[k++]=a[i++];//可能会有多余的，补上
    while(j<=r) b[k++]=a[j++];
    for(i=l;i<=r;i++){//放回去
          a[i]=b[i-l+1];
    }
    return;
}
int main(){
        cin >> www >> n;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        merge_sort(1,n);//n个数，从1到n
        for(int i=1;i<=n;i++) printf("%d ",a[i]);
        return 0;
}