归并排序

题目描述

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在$1$ ~$ 10^9$范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

$1≤n≤1000001≤n≤100000$

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

题目分析

归并排序相对于快速排序更稳定

确定分界点取中间值mid = (l + r) >> 1

归并排序左右两边

将左右两边合二为一

指针从两边的开头同时开始，取数比较

取出最小的放入新数组，指针向后移

直到一个指针走到当前段的末尾为止若某一段指针已到了末尾，另一段指针还在一半，将直接将剩下一半依次放入新数组

将新数组值放回原数组

代码实现

#include<iostream>
using namespace std;

const int N = 1e6 + 10;

int n;
int a[N],temp[N];

void merge_sort(int l, int r, int a[]){
    // 判断边界，如果传入数组长度是否小于等于1
    if(l >= r)  return;
    // 1. 确定分界点
    int mid = l + r >> 1;
    // 2. 归并排序左右两边
    merge_sort(l, mid, a);
    merge_sort(mid + 1, r, a);
    int k = 0;  // 表示当前 temp 中有多少个元素
    // 3. 定义左右指针起始位置
    int i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        // 比较左右两端最小值放入新数组
        if(a[i] < a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    // 判断两边元素是否到头
    while(i <= mid) temp[k++] = a[i++];
    while(j <= r) temp[k++] = a[j++];
    // 4. 将元素复制回原数组
    for(i = l, j = 0; i <= r; i++,j++)
        a[i] = temp[j];
}

int main(){
    //输入元素个数
    scanf("%d", &n);
    //填充数组
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    //归并排序
    merge_sort(0, n - 1, a);
    //打印数组
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
}

运行结果

输入

6
3 1 2 4 5 7

输出

1 2 3 4 5 7

总结

归并排序与快速排序最大的差距是分界点的问题，其次是对左右两边分别进行归并排序，然后将左右两边的分别比较出来，依次找出最小值，将其顺次放入到新数组里，最终再整合复制到原数组里进行输出。