[数据结构与算法]排序算法-归并排序

了解归并排序之前复习一下递归

递归

递归可以把大的问题,分解成小问题.

需要结束条件,否则递归无法结束.每次递归都需要在栈上开辟新空间.

#include <iostream>

using namespace std;

int factorial(int num)
{
	if (num == 1)	//结束条件
	{
		return 1;
	}
	return num * factorial(num - 1);
}

int main()
{
	cout << factorial(10) << endl;

	return 0;
}

归并排序

原理

分组分到不能分为止,进行排序合并,就是归并排序.

时间复制度O(NlogN)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//前置声明
void myMerge(vector<int>& v, int min, int mid, int max);

//递归进行分割然后合并
void myPartition(vector<int>& v, int min, int max)
{
	if (min == max)	//退出条件 也就是分割到为1时
	{
		return;
	}

	//当 5-10 中间为5+2 = 7
	int mid = min + (max - min) / 2;
	//分割左半部分
	myPartition(v, min, mid);
	//分割右半部分
	myPartition(v, mid + 1, max);
	//合并排序
	myMerge(v, min, mid, max);
}

void myMerge(vector<int>& v, int min, int mid, int max)
{
	//开辟一个新空间存放排序序列 多少个数就开辟多大空间(他的空间大小不一定时size,是在变的)
	vector<int> temp(max - min + 1);
	int index = 0;
	int left_index = min;
	int right_index = mid + 1;
	//左右下标有一方越界则停止循环
	while (left_index <= mid && right_index <= max)
	{
		//左右两边谁小谁赋值
		temp[index++] = (v[left_index] <= v[right_index] ? v[left_index++] : v[right_index++]);
	}
	
	//左右两边只会执行一边
	//左边未越界将左边全部依次放入容器中
	while (left_index <= mid)
	{
		temp[index++] = v[left_index++];
	}
	//有边未越界将左边全部依次放入容器中
	while (right_index <= max)
	{
		temp[index++] = v[right_index++];
	}

	for (int i = 0; i < temp.size(); i++)
	{
		//赋值到最左边所以min是有序的
		v[min + i] = temp[i];
	}
}

void mergeSort(vector<int>& v)
{
	//没有元素或元素少于两个不需要排序
	if (v.empty() || v.size() < 2)
	{
		return;
	}

	myPartition(v, 0, v.size() - 1);
}

int main()
{
	vector<int> v = { 32,4,7,24,5,245,7,245,657,28 };

	mergeSort(v);
	for (auto val : v)
	{
		cout << val << " ";
	}
	cout << endl;

	return 0;
}