一起学习交流~

排序-05-归并排序的两种实现

算法 laomuji 12个月前 (10-09) 344次浏览 已收录 0个评论

一、什么是归并排序

先上百度百科 归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要。归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数。

二、算法描述

继续百度百科 归并操作的工作原理如下:
第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置
第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

设有数列{6,202,100,301,38,8,1}
初始状态:6,202,100,301,38,8,1
第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

三、代码实现

了解之后,我们先实现简单的归并排序

//用vector数组,方便理解,但是这种方法很慢
vector<int>Merge(vector<int>leftArray, vector<int>rightArray)
{
	//用于返回的数组
	vector<int>rArray;
	//两个下标,都从第一个数字开始
	int leftPos = 0;
	int rightPos = 0;
	//首先是两个数组都没有到结尾的情况,逐个进行比较
	while(leftPos < leftArray.size() && rightPos < rightArray.size())
	{
		if (leftArray[leftPos] < rightArray[rightPos]) 
		{
			//左边小就把左边加入,并且往右移动
			rArray.push_back(leftArray[leftPos]);
			leftPos++;
		}
		else if (rightArray[rightPos] < leftArray[leftPos])
		{
			//右边小就把右边加入,并且往右移动
			rArray.push_back(rightArray[rightPos]);
			rightPos++;
		}
		else 
		{
			//相等就两边都加入,都往右移动
			rArray.push_back(leftArray[leftPos]);
			leftPos++;
			rArray.push_back(rightArray[rightPos]);
			rightPos++;
		}
	}
	//如果某个数组没有到结尾,就把剩下的数据加进去,两个数组中只可能有一个有剩余
	while (leftPos < leftArray.size())
	{
		rArray.push_back(leftArray[leftPos]);
		leftPos++;
	}
	while (rightPos < rightArray.size())
	{
		rArray.push_back(rightArray[rightPos]);
		rightPos++;
	}
	return rArray;
}

//将数组每次分为2个数组,直到就剩1或0个不需要排序为止
vector<int> MergeSort(vector<int>nums) 
{
	//一直递归 直到就剩1个或0个为止
	//归并排序的优化思路 就是当数组个数小于某个数的时候使用其它的排序
	if (nums.size() < 2)return nums;
	int mid = nums.size() / 2;
	//分成左右两个数组
	vector<int>leftArray = MergeSort(vector<int>(nums.begin(), nums.end() - mid));
	vector<int>rightArray = MergeSort(vector<int>(nums.end() - mid, nums.end()));
	//合并数组并返回
	return Merge(leftArray,rightArray);
}

首先递归将数组不停的分成两个左边数组和右边数组,

直到数组中只剩下一个元素停止递归

假设有数组{ 1,9,2,8,3,7,4,6,5,10 }

不停的将数组分为两组,然后进行合并

通过对上面的简单理解,接下来是正常的归并排序代码

//通过startPos endPos midPos就可以推测出两个数组的区域
//startPos到midPos为第一组
//midPos+1到endPos为第二组
void merge(int* sourceArray, int* tempArray, int startPos, int endPos, int midPos)
{
	int* leftArray = sourceArray + startPos;//左边数组的位置
	int* rightArray = sourceArray + midPos + 1;//右边数组的位置
	int leftArraySize = midPos - startPos + 1;//左边数组的个数,不是坐标
	int rightArraySize = endPos - (midPos + 1) + 1;//右边数组的个数不是坐标
	int leftPos = 0;//左边数组下标
	int rightPos = 0;//右边数组下标
	int tempArrayPos = startPos;//临时数组的下标

	////如果两个数组都没有到结尾
	while (leftPos < leftArraySize && rightPos < rightArraySize)
	{
		if (leftArray[leftPos] < rightArray[rightPos])
		{
			//如果左边小就加入左边,并且移动左边
			tempArray[tempArrayPos++] = leftArray[leftPos++];
		}
		else if (leftArray[leftPos] > rightArray[rightPos]) {
			//如果右边小就加入左边,并且移动右边
			tempArray[tempArrayPos++] = rightArray[rightPos++];
		}
		else
		{
			//如果两边一样大 就一起加入并且一起移动
			tempArray[tempArrayPos++] = leftArray[leftPos++];
			tempArray[tempArrayPos++] = rightArray[rightPos++];
		}
	}
	//如果某个数组没有到结尾,就把剩下的数据加进去,两个数组中只可能有一个有剩余
	while (leftPos < leftArraySize)tempArray[tempArrayPos++] = leftArray[leftPos++];
	while (rightPos < rightArraySize)tempArray[tempArrayPos++] = rightArray[rightPos++];
	//注意 一定得把数据拷贝到sourceArray中,运算都依赖于sourceArray
	for (int i = startPos; i <= endPos; i++)sourceArray[i] = tempArray[i];
}

//归并
void mergeSort(int* sourceArray, int *tempArray,int startPos,int endPos)
{
	int size = endPos - startPos;//个数
	//如果个数小于2 表示不需要再分了
	//if (size < 2)return;
	if (startPos >= endPos)return;
	int midPos = (startPos + endPos) / 2;//中间位置,将数组切割成两个
	mergeSort(sourceArray, tempArray, startPos, midPos);//startPos到midPos为第一组
	mergeSort(sourceArray, tempArray, midPos + 1, endPos);//midPos+1到endPos为第二组

	//将两个数组合并
	merge(sourceArray, tempArray, startPos, endPos, midPos);
}

int main()
{
	int num[] = { 1,9,2,8,3,7,4,6,5,10 };
	int temp[10];
	mergeSort(num,temp,0,9);
	for (int i= 0; i < 10; i++)
	{
		cout << num[i]<<" ";
	}
}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论