[C++知识库]C/C++语言100题练习计划 89——归并排序（分治法实现）

名人说：博学之，审问之，慎思之，明辨之，笃行之。——《中庸》
进度：C/C++语言100题练习计划专栏，目前89/100

🥇C/C++语言100题练习专栏计划：目的：巩固练习C/C++语言，增强上机、动手实践能力，交流学习！

一、问题呈现

1.问题描述

Problem Description

输入一个含有n个元素的数列，输出归并排序后的结果。（升序输出）

2.输入输出

Input

第一行：一个整数n，表示数列中元素的个数。(0< n <=1000)
第二行：n个数列元素。

Output
第一行：输出排序后的数列

3.测试样例

Sample Input

8
42 15 20 6 8 38 50 12

Sample Output

6 8 12 15 20 38 42 50

二、源码实现

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

//归并(合并)函数
void Merge(int a[],int low,int mid,int high)
{
    int *b=new int [high-low+1];//申请一个跟数组a同大小的辅助数组
    int i=low; //将i指向第一分段的最左边元素
    int j=mid+1; //将j指向第二分段的最左边元素
    int k=0; //k指向辅助数组首元素下标
    
    while(i<=mid && j<=high)//将数组a中的元素按从小到大的顺序存放到辅助数组b中
    {
        if(a[i]<=a[j])
        {
            b[k++]=a[i++];
        }
        else
        {
            b[k++]=a[j++];
        }
    }

 	//这两个while是处理数组a剩下的元素，因为分段之后数组大小未必一样大。   
 	//并通过这两个while循环将其复制到B数组中去。 
    while(i<=mid)
    	b[k++]=a[i++];

    while(j<=high)
        b[k++]=a[j++];
    
    //此时数组b中是排好序的元素序列，将其所有元素复制到数组a中
	for(i=low,k=0;i<=high;i++)
    {
        a[i]=b[k++];
    }
    
    //使用完数组b之后，将其释放掉
    delete []b;
}

//归并(合并)排序
void MergeSort(int a[],int low,int high)
{
    if(low<high)
    {
        int middle=(low+high)/2;//取中点
        MergeSort(a,low,middle); //将第一段A[low:mid]进行合并排序（分治递归）
        MergeSort(a,middle+1,high); //将第二段A[mid+1:high]进行合并排序
        Merge(a,low,middle,high);//最终合并完成后复制到A辅助数组
    }
}

//主函数
int main()
{
	//对数组a以及变量n进行声明定义
    int a[1005];
    int n;
    
    //输入元素的个数n
    cin >> n;
	//输入数组序列中的元素
    for (int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    
    //调用归并(合并)排序函数，对数组中序列元素进行排序
	MergeSort(a,0,n-1);
    
	//输出归并排序之后的结果（升序）
    for (int i=0;i<n;i++)
    {
        cout << a[i] << " " ;
    }
    
    //输出换行
	cout << endl;
    return 0;
}

★关于本题思路及归并排序：

1、本题思路简述

题意：输入一个含有n个元素的数列，输出归并排序后的结果。（要求：降序排序）
从问题描述来看，要使用归并排序进行排序，归并排序是采用分治法实现对n个元素进行排序的算法，是分治法的一个典型应用。可以大致分解出以下过程：
①分解
将待排序的元素分成大小大致相同的两个子序列。
②治理
将两个子序列进行归并排序(合并排序)。
③合并
将排序好的有序子序列进行合并，得到最终的有序序列。
在这三步操作之后会得到一个有序序列，至于输出时是升序还是降序，可以通过调节循环条件的写法，来按要求输出，比如升序转降序可以将初始的循环条件i=0;i<n;i++可以改为i=n-1;i>=0;i–，降序转升序同理。（方法不一）。

2、归并排序

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

1??关于归并排序的理解
归并排序，大致思想其实就是先将数组中的元素拆分成若干小部分，然后再将这些小部分按照顺序进行重新归并，从而实现排序。根据分治法的思想（“分而治之”），即将一个大问题分成若干个相同的小问题，因为问题规模变小了，所以解决问题的难度也相应地会减小一些。其实可以试想一下，对一个拥有1000个元素的数组进行排序简单还是对一个只拥有1个元素的数组进行排序简单？答案很明显。

2??举例
例如：对42 15 20 6 8 38 50 12进行归并排序

gif动图演示?

三、测试结果

8
42 15 20 6 8 38 50 12
6 8 12 15 20 38 42 50

--------------------------------
Process exited after 1.857 seconds with return value 0
请按任意键继续. . .

Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder）
如果对大家有帮助的话，希望大家能多多点赞+关注！这样我动力会更足哦！ ?( ′･?･` )比心