资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

c++如何实现二路归并排序

这篇文章主要讲解了“c++如何实现二路归并排序”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“c++如何实现二路归并排序”吧!

网站建设哪家好,找创新互联!专注于网页设计、网站建设、微信开发、微信小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了淅川免费建站欢迎大家使用!

二路归并排序

基本思想

二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并:两个有序表放在同一数组的相邻位置上,arr[left]到arr[center-1]为第一个有序表,arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较,小的先放在一个temp数组,最后将比较剩下的直接放到temp中去,最后将temp又复制回arr。这是“治”。
所谓“分”,就是递归地将前半部分和后半部分的数据各自归并排序即可。

算法分析

每一趟归并的时间复杂度为O(n),共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外,归并排序中归并的算法并不会将相同关键字的元素改变相对次序,所以归并排序是稳定的。
二路归并排序的前提是两个序列本身有序。

void Merger(int *arr, int len, int width)
{
 int *temp =(int *)malloc(sizeof(int) * (len));
 //首先对两路下标分别进行初始化
 int l1 = 0;
 int h2 = l1 + width - 1;
 int l2 = h2 + 1;
 int h3 = l2 + width - 1 < len - 1 ? l2 + width - 1 : len - 1;
 int temppos = 0;
 //判断所在下标位置的值
 while (l1 < len && l2 < len)
 {
 while (l1 <= h2 && l2 <= h3)
 {
  if (arr[l1] < arr[l2])
  {
  temp[temppos++] = arr[l1++];
  }
  else
  {
  temp[temppos++] = arr[l2++];
  }
 }
 //l1有剩余
 while (l1 <= h2)
 {
  temp[temppos++] = arr[l1++];
 }
 //l2有剩余
 while (l2 <= h3)
 {
  temp[temppos++] = arr[l2++];
 }
 //l1 l2向后移动
 l1 = h3 + 1;
 h2 = (l1 + width - 1) < (len - 1) ? (l1 + width - 1) : (len - 1);
 l2 = h2 + 1;
 h3 = (l2 + width - 1) < (len - 1) ? (l2 + width - 1) : (len - 1);
 }
 //奇数归并块 剩下的一个单都块操作
 while (l1 

PS:二路合并排序算法

#include
using namespace std;
class SortableList
{
public:
	SortableList(int mSize)
	{
		maxSize = mSize;
	  l= new int[maxSize];
		n = 0;
	}
	~SortableList()
	{
		delete[]l;
	}
	void Merge(int, int, int);
	void MergeSort(int,int);
	void Input();
	void Output();
	
   private:
		 int* l;
		 int maxSize;
		 int n;

};
void SortableList::Input()
{
	cout << "请输入要排序的数:";
	for (int i = 0; i <= maxSize - 1; i++)
		cin >> l[i];
}
void SortableList::Output()
{
	cout << "排序后的数是:";
	for (int i = 0; i <= maxSize - 1; i++)
		cout << l[i]<<' ';
}
void SortableList::MergeSort(int left,int right)
{
	if (left < right)//如果序列长度大于1则划分
	{
		int mid = (left + right) / 2;
		MergeSort(left, mid);//对左序列进行排序
		MergeSort(mid + 1, right);//对右序列进行排序
		Merge(left, mid, right);//合并
	}
}
void SortableList::Merge(int left, int mid, int right)
{
	int* temp= new int[right - left + 1];
	int i = left, j = mid + 1, k = 0;
	while ((i <= mid) && (j <= right))//判断序列是否为空
		if (l[i] <= l[j])
			temp[k++] = l[i++];
		else temp[k++] = l[j++];
	while (i <= mid)
		temp[k++] = l[i++];//右序列空了左序列依次写入
	while (j <= right)
		temp[k++] = l[j++];//左序列空了右序列依次写入
	for (i = 0, k = left; k <= right;)
		l[k++] = temp[i++];//临时在数组temp中的排列好的数据放入数组l
}
int main()
{
	int m;
	cout << "请输入要排序的数的数目:";
	cin >> m;
	SortableList a1(m);
	a1.Input();
	a1.MergeSort(0, m-1);
	a1.Output();
}

感谢各位的阅读,以上就是“c++如何实现二路归并排序”的内容了,经过本文的学习后,相信大家对c++如何实现二路归并排序这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!


新闻标题:c++如何实现二路归并排序
本文地址:http://www.cdkjz.cn/article/peeihs.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220