【原】基本算法-归并排序

翟天保的图书馆 2022-07-08 发布于上海

展开全文

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

前言

本文介绍一种排序算法——归并排序，是常用的排序算法之一。以下是本篇文章正文内容，包括算法简介、算法特点、算法实现和C++示例。

一、归并排序简介

归并排序法是将已排序好的两个或多个数列，通过合并的方式组合成一个更大的且排好序的数列。

归并排序法的实现思路有很多，本文介绍其中一种（我觉得最好理解且最方便实现的）——2路拆分法。

将数列拆分为N个长度为1的数列。
两两合并并排序，形成N/2个长度为2的数列。
继续两两合并并排序，形成N/4个长度为4的数列。
以此类推，直到形成长度为N的总数列，完成排序。

二、算法特点

1）归并排序n个数据，一般需要处理log2n次，每次处理的时间复杂度为O(n)。因此，最坏最好和平均的时间复杂度都是O(nlog2n)。

2）稳定，合并过程不改变原序列过程。

3）空间复杂度是O(n)，需要用一个同样尺寸的额外空间做辅助。

三、代码实现

代码实现逻辑：

递归拆分。
从最小长度开始合并。
合并完成则排序完成。

// 合并
void Merge(vector<int> &data, int left, int mid, int right)
{
	vector<int> temp(right - left + 1, 0);
	int i = left;
	int j = mid + 1;
	int k = 0;

    // 比较填补
	while (i <= mid && j <= right)
	{
		if (data[i] <= data[j])
			temp[k++] = data[i++];
		else
			temp[k++] = data[j++];
	}

    // 剩余填补
	while (i <= mid)
		temp[k++] = data[i++];
	while (j <= right)
		temp[k++] = data[j++];

    // 拷贝
	for (int i = 0; i < k; ++i)
		data[i + left] = temp[i];
}

// 拆分
void Split(vector<int> &data, int left, int right)
{
    // 拆分至长度1返回
	if (left >= right)
		return;
	int mid = (left + right) / 2;

    // 递归
	Split(data, left, mid);
	Split(data, mid + 1, right);
	Merge(data, left, mid, right);
}

// 归并排序
void MergeSort(vector<int> &data)
{
	int size = static_cast<int>(data.size());
	int mid = size / 2;

    // 递归
	Split(data, 0, mid);
	Split(data, mid + 1, size - 1);
	Merge(data, 0, mid, size - 1);
}

四、C++示例

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>

using namespace std;

// 展示当前顺序
void Show(vector<int> data)
{
	size_t size = data.size();
	for (size_t i = 0; i < size; ++i)
		cout << setw(4) << data[i];
	cout << endl;
}

// 合并
int Mcount = 1;
void Merge(vector<int> &data, int left, int mid, int right)
{
	vector<int> temp(right - left + 1, 0);
	int i = left;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= right)
	{
		if (data[i] <= data[j])
			temp[k++] = data[i++];
		else
			temp[k++] = data[j++];
	}
	while (i <= mid)
		temp[k++] = data[i++];
	while (j <= right)
		temp[k++] = data[j++];

	for (int i = 0; i < k; ++i)
		data[i + left] = temp[i];
	cout << "第" << Mcount << "次排序结果：\n";
	Show(data);
	Mcount++;
}

// 拆分
void Split(vector<int> &data, int left, int right)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	Split(data, left, mid);
	Split(data, mid + 1, right);
	Merge(data, left, mid, right);
}

// 归并排序
void MergeSort(vector<int> &data)
{
	cout << "归并排序：\n原始数据：\n";
	Show(data);
	int size = static_cast<int>(data.size());
	int mid = size / 2;
	Split(data, 0, mid);
	Split(data, mid + 1, size - 1);
	Merge(data, 0, mid, size - 1);
	cout << "排序后结果：\n";
	Show(data);
}

// 主函数
int main()
{
	vector<int> data = { 9,11,567,0,-2,4,2,12,18,6,9 };

	// 归并排序
	MergeSort(data);

	system("pause");
	return 0;
}

效果图：