? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 归并排序（MergeSort）

一、归并排序是建立在分治法的基础上进行的排序。归并排序的思想是：先将一组数据进行分割成若干的小子序列，然后将这些子序列进行排序，之后再对这些子序列再进行排序。当将两个子序列合并成一个有序子序列，称之为二路归并。

在进行归并排序时需要进行三步：①：针对两个有序子序列的合并

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ②：针对一趟所有子序列的合并

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ③：循环使得子序列越来越少最终全部合并完毕

针对第一个步骤①：当所有子序列的元素个数都是1时，那么每个子序列都是有序的。因此第一次就是两个元素（也是两个子序列）进行合并。

针对第二个步骤②：就是把所有子序列进行两两合并（注意：第一次就是把所有的元素两两合并）

针对第三个步骤③：由于是二路归并所以每一趟合并的子序列就是上一次长度的二倍。所以此次循环O(logn)次

二、代码如下：

头文件：

#pragma once
#include<ctime>
#include<malloc.h>
#include<iostream>
using namespace std;

//将两个有序子序列合并
void merge(int arr[], int small, int mid, int big);

//进行一趟子序列的全排序
void OneMerge(int arr[], int length, int size);

//进行归并排序
void MergeSort(int arr[], int size);

//打印
void PrintMergeSort(int array[], int size);

函数体：

#include"MergeSort.h"

//将两个有序子序列合并
void merge(int arr[], int small, int mid, int big)
{
	//创建一个临时数组来存储排序后的子序列
	int* ptr = (int*)malloc(sizeof(int)*(big - small + 1));
	int i = small;//0
	int j = mid + 1;//2
	int k = 0;
	while (i <= mid && j <= big)
	{
		if (arr[i] <= arr[j])
		{
			ptr[k++] = arr[i++];
		}
		else
		{
			ptr[k++] = arr[j++];
		}
	}
	while (i <= mid)
	{
		ptr[k++] = arr[i++];
	}
	while (j <= big)
	{
		ptr[k++] = arr[j++];
	}
	for (i = small, k = 0; i <= big; k++, i++)
	{
		arr[i] = ptr[k];
	}
	free(ptr);
	ptr = nullptr;
}

//进行一趟子序列的全排序
void OneMerge(int arr[], int length, int size)
{
	int i;
	for (i = 0; i + 2 * length - 1 < size; i = i + 2 * length)
	{
		merge(arr, i, i + length - 1, i + 2 * length - 1);
	}
	if (i + length - 1 < size)
	{
		merge(arr, i, i + length - 1, size - 1);
	}
}

//进行归并排序
void MergeSort(int arr[], int size)
{
	for (int i = 1; i <= size; i *= 2)
	{
		OneMerge(arr, i, size);
	}
}

//打印
void PrintMergeSort(int array[], int size)
{
	int i = 0;
	while (i < size)
	{
		cout << array[i++] << " ";
	}
	cout << endl;
}

主函数：

#include"MergeSort.h"

#define ARRA_YSIZE 100

int main()
{
	srand((unsigned int)time(NULL));
	int array[ARRA_YSIZE];
	for (int i = 0; i < ARRA_YSIZE; i++)
	{
		array[i] = rand() % 100;
	}
    int size = sizeof(array) / sizeof(array[0]);
	cout << "未排序：";
	PrintMergeSort(array, size);
	MergeSort(array, size);
	cout << "归并排序：";
	PrintMergeSort(array, size);
	system("pause");
	return 0;
}

结果显示：

三、归并排序的特性：

? ? ? ? ?①：归并排序的不足在于它需要借助O(N)的空间复杂度。归并排序可以解决当数据达到无法全部加载进内存的数据的排序。

? ? ? ? ?②：时间复杂度O(nlogn)

? ? ? ? ?③：空间复杂度O(n) --->需要借助空间来存放合并的子序列

? ? ? ? ?④：归并排序是一种稳定的排序算法? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 珍&源码