归并排序算法

题目

给定一个长度为 n 的整数数列,请你使用归并排序对这个数列按照从小到大进行排序,并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n
第二行包含 n个整数（所有整数均在 1∼109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

归并排序介绍

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
自下而上的迭代；

归并排序的核心

归并排序的核心思想是将一个大问题分解成若干个小问题，分别解决这些小问题，然后将结果合并起来，最终得到整个问题的解。具体到排序问题，归并排序的步骤如下：

1. 分解（Divide）：将待排序的数组分成两个子数组，每个子数组包含大约一半的元素。

2. 解决（Conquer）：==递归地==对每个子数组进行排序。

3. 合并（Combine）：将两个已排序的子数组==合并==成一个有序的数组。

通过不断地分解和合并，最终整个数组将被排序。

归并排序的过程模拟

假设有一个待排序的列表 [38, 27, 43, 3, 9, 82, 10]，归并排序的过程如下：

• 将列表分成两半：[38, 27, 43, 3] 和 [9, 82, 10]。
• 继续分解：[38, 27, 43, 3] 分成 [38, 27] 和 [43, 3]，[9, 82, 10] 分成 [9] 和 [82, 10]。
• 继续分解：[38, 27] 分成 [38] 和 [27]，[43, 3] 分成 [43] 和 [3]，[82, 10] 分成 [82] 和 [10]，最终分解为单个元素的子列表。

合并：
- 合并 [38] 和 [27] 得到 [27, 38]。
- 合并 [43] 和 [3] 得到 [3, 43]。
- 合并 [27, 38] 和 [3, 43] 得到 [3, 27, 38, 43]。
- 合并 [9] 和 [10, 82] 得到 [9, 10, 82]。
- 合并 [3, 27, 38, 43] 和 [9, 10, 82] 得到最终有序列表 [3, 9, 10, 27, 38, 43, 82]。

C++实现代码：

/*
归并排序：分治思想
将数组分为小数组并且排序后重组 
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

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

void merge_sort(int a[],int l,int r)
{
    if(l>=r)
    return ;
    int mid = l+r>>1;
    //递归排序左半边数组
    merge_sort(a,l,mid);
    //递归排序右半边数组
    merge_sort(a,mid+1,r);

    //遍历合并数组
    int i = l,j = mid+1;
    int k = 0;
    //左右半边都没遍历完
    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++];
    //把临时数组中的元素拷贝至原数组
    for(int i = l,k=0;i<=r;++i)
    a[i] = temp[k++];
}

int main()
{
    scanf("%d",&n);
    for(int i = 0;i <n ;++ i)
    scanf("%d",&a[i]);
    merge_sort(a,0,n-1);
    for(int i = 0;i<n;++i)
    printf("%d ",a[i]);

    return 0;
}