[数据结构与算法] 常见排序算法之归并排序—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 常见排序算法之归并排序——归并排序 -> 正文阅读

[数据结构与算法]常见排序算法之归并排序——归并排序

? ??? ???

哈喽大家好，我是保护小周?，本期为大家带来的是常见排序算法中的归并排序，博主在这里先分享归并排序的递归算法，包您一看就会，快来试试吧~

?一、归并排序

1.1 基本思想

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

1.2 算法思想

到这里，我们可以得到一条结论，两个有序的子序列可以合成一个新的有序子序列，通过递归，我们两个新的有序序列也可以组成新的有序数列，最终实现排序的目的。有些朋友就会问了，这个我懂，关键是咋实现有序数列，其实非常的简单，分割递归至每个子序列只有一个元素时，是不是就有序啦，然后就可以合成有两个元素有序的列表嘛，再合成4个，8个……

1.3 程序设计思想

定义一个tmp数组，可以是动态开辟的(malloc)，用于临时存放合并后的有序数据，定义_MergeSort()函数，用于分解，合并数据（递归实现），参数有，待处理数组，数据区间（数组下标），tmp数组。

判断区间是否存在，区间不存在以及只有一个元素的情况结束程序。
分割区间：mid=(left+right)/2;递归左右区间，分割递归至每个子序列只有一个元素。
每两个子序列一组，循环遍历每一个元素，if比较两个子序列各元素的大小，取大或取小，放入tmp数组，tmp[index++]=子序列++；直到有一个子序列遍历完，循环结束。
循环判断是子序列是否遍历完毕，未遍历完毕的子序列剩余元素直接给到tmp数组。
将tmp数组的对应的元素拷贝回原数组（已有序）。

1.4 程序实现

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>//动态开辟空间的函数的头文件

void _MergeSort(int *a,int left,int right,int *tmp)
{
	//区间不存在以及只有一个元素的情况结束程序
	if (left>=right)
	{
		return;
	}

	int mid = (left + right) / 2;
	//假设[left,mid],[mid+1,right]有序，那么我们就可以归并了
	//递归使左右区间有序
	//分割递归至每个子序列只有一个元素
	_MergeSort(a,left,mid,tmp);
	_MergeSort(a, mid+1,right, tmp);

	//归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;

	while (begin1<=end1&&begin2<=end2)//有一个子序列遍历完，循环结束
	{
		if (a[begin1] < a[begin2])//升序，取小
		{
			tmp[index++] = a[begin1++];

		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}

	//判断子序列是否遍历完，未遍历完毕的子序列剩余元素直接给到tmp数组
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}

	while (begin2<=end2)
	{
		tmp[index++] = a[begin2++];
	}

	//拷贝回去
	for (int i=left;i<=right;++i)
	{
		a[i] = tmp[i];
	}
}

//归并排序
void MergeSort(int *a,int n)
{
	int* tmp=(int*)malloc(sizeof(int)*n);//动态开辟与待排序数组大小相等的一片连续的空间
	_MergeSort(a,0,n-1,tmp);//子函数实现归并

	free(tmp);//释放动态开辟的空间
}

//打印
void Print(int* a, int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
int main()
{
	int a[] = {10,6,7,1,3,9,4,2};
	MergeSort(a,sizeof(a)/sizeof(a[0]));
	Print(a,sizeof(a)/sizeof(a[0]));
	return 0;
}