C++排序算法：归并排序详解

        目录

一、归并排序

二、基本算法

        1、分离

        2、合并

        3、图片讲解

三、代码实现

        1、分离函数

        2、合并函数 

        3、完整代码 

        4、样例

四、总结

一、归并排序

        归并排序(Merge Sort)是建立在归并操作上的一种既有效又稳定的排序算法，该算法是采用

分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的

序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二

路归并。

二、基本算法

        1、分离

                     将已有数列不断分离成两段长度基本相同（当已有数列长度是奇数时，则一半长一半短），直到分离成长度为 1 的 n 个数列（其实就是 n 个数）。

        2、合并

                     将数列两两合并，每次合并时进行比较和排序，直到完成排序。

        3、图片讲解

                     将一个无序数列排好序：

                   先是分离成长度为 1 的 n 个数列，然后再合并，合并过程中两个红色区域代表两两比较，然后将小的放在前面。

三、代码实现

        1、分离函数

void mergesort(int x,int y)			//分离，x 和 y 分别代表要分离数列的开头和结尾
{
	if (x>=y) return;        //如果开头 ≥ 结尾，那么就说明数列分完了，就要返回
	int mid=(x+y)/2;            //将中间数求出来，用中间数把数列分成两段
	mergesort(x,mid);
	mergesort(mid+1,y);        //递归，继续分离
	merge(x,mid,y);        //分离玩之后就合并
}

        2、合并函数 

void merge(int low,int mid,int high) //归并
//low 和 mid 分别是要合并的第一个数列的开头和结尾，mid+1 和 high 分别是第二个数列的开头和结尾
{
	int i=low,j=mid+1,k=low;
    //i、j 分别标记第一和第二个数列的当前位置，k 是标记当前要放到整体的哪一个位置
	while (i<=mid && j<=high)    //如果两个数列的数都没放完，循环
	{
		if (a[i]<a[j])
			b[k++]=a[i++];
		else
			b[k++]=a[j++];   //将a[i] 和 a[j] 中小的那个放入 b[k]，然后将相应的标记变量增加
	}        // b[k++]=a[i++] 和 b[k++]=a[j++] 是先赋值，再增加
	while (i<=mid)
		b[k++]=a[i++];
	while (j<=high)
		b[k++]=a[j++];    //当有一个数列放完了，就将另一个数列剩下的数按顺序放好
	for (int i=low;i<=high;i++)
		a[i]=b[i];                //将 b 数组里的东西放入 a 数组，因为 b 数组还可能要继续使用
}

        3、完整代码 

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int n,a[12000],b[12000];
void merge(int low,int mid,int high)
{
	int i=low,j=mid+1,k=low;
	while (i<=mid && j<=high)
	{
		if (a[i]<a[j])
			b[k++]=a[i++];
		else
			b[k++]=a[j++];
	}
	while (i<=mid)
		b[k++]=a[i++];
	while (j<=high)
		b[k++]=a[j++];
	for (int i=low;i<=high;i++)
		a[i]=b[i];
}
void mergesort(int x,int y)
{
	if (x>=y) return;
	int mid=(x+y)/2;
	mergesort(x,mid);
	mergesort(mid+1,y);
	merge(x,mid,y);
}
int main()
{
	cin >>n;
	for (int i=1;i<=n;i++)
		cin >>a[i];
	mergesort(1,n);  //调用函数
	for (int i=1;i<=n;i++)
		cout <<a[i] <<" ";
	return 0;
}

        4、样例

        输入：

5

5 8 1 3 4

        输出：

 1 3 4 5 8 

四、总结

        今天我们学习了排序中又快又稳定的算法：归并排序，时间复杂度为 O（nlogn） 。代码很简洁，很容易懂，点个赞再走吧！

        另外，想了解排序的稳定性，请移步至：

C++——排序的稳定性_闪耀的天狼星的博客-CSDN博客排序算法的稳定性https://blog.csdn.net/DUXS11/article/details/125468174?spm=1001.2014.3001.5501文章来源地址https://www.toymoban.com/news/detail-655305.html

到了这里，关于C++排序算法：归并排序详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！