归并排序—C++实现-创新互联

我始终相信一句话：只有自己足够强大。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：主机域名、网站空间、营销软件、网站建设、济阳网站维护、网站推广。

归并排序

• 一、分治思想
• 二、归并排序实现
• 三、代码展示

一、分治思想

分治，就是把一个问题分成多个相似或相同的子问题，直到子问题可以简单的解决。
归并排序就是运用了这个分治思想，通过递归把要排序的元素分成多个子序列，l记录起始位置，r记录末尾位置，在进行循环，去判断大小，从而完成排序。

二、归并排序实现

要排序得先开数组，在输入数据

代码如下（示例）：

const int N = 1e6 + 10;

int q[N], tmp[N];

int n;

	cin >>n;
	for (int i = 0; i< n; i++)
	{cin >>q[i];
	}

在这里，用了一个临时数组tmp，是为了把排序元素存在这个数组里，最后在赋值给原始数组。

找一个分界点，每次递归把元素分开，直到 l>=r 不符合条件为止，起始位置怎么可能>= 末尾位置。

if (l >= r)
	{return;
	}

	int mid = l + r >>1; //这个等价于(l + r) /2;

注：+ 的优先级是要比 >>高的，所以不用带括号。

然后进行递归

MergeSort(q, l, mid);
	MergeSort(q, mid + 1, r);

这样，就能把数组的元素分开了。分开之后，mid左边的，起始位置就是l，末尾位置就是mid。
mid右边的，起始位置就是mid + 1，末尾位置就是r。

然后进行排序，先把小的元素给tmp，大的元素最后在给

int i = l;
	int j = mid + 1;
	int k = 0;
	while (i<= mid && j<= r)
	{if (q[i]<= q[j])
		{	tmp[k++] = q[i++];
		}
		else
		{	tmp[k++] = q[j++];
		}
	}

i走到头或者j走到头，但是还有元素没有放在tmp里怎么办

while (i<= mid)
	{tmp[k++] = q[i++];
	}
	while (j<= r)
	{tmp[k++] = q[j++];
	}

在进行判断就🆗了，

就是这样，就可以把所有元素放在tmp数组里了。

最后把tmp里的元素给q，就完成了。

for (int i = l, j = 0; i<= r; i++)
	{q[i] = tmp[j++];
	}

三、代码展示

#includeusing namespace std;

const int N = 1e6 + 10;

int q[N], tmp[N];

int n;

void MergeSort(int q[], int l, int r)
{if (l >= r)
	{return;
	}

	int mid = l + r >>1;
	MergeSort(q, l, mid);
	MergeSort(q, mid + 1, r);
	int i = l;
	int j = mid + 1;
	int k = 0;
	while (i<= mid && j<= r)
	{if (q[i]<= q[j])
		{	tmp[k++] = q[i++];
		}
		else
		{	tmp[k++] = q[j++];
		}
	}

	while (i<= mid)
	{tmp[k++] = q[i++];
	}
	while (j<= r)
	{tmp[k++] = q[j++];
	}

	for (int i = l, j = 0; i<= r; i++)
	{q[i] = tmp[j++];
	}
}

int main()
{cin >>n;
	for (int i = 0; i< n; i++)
	{cin >>q[i];
	}

	MergeSort(q, 0, n - 1);

	for (int i = 0; i< n; i++)
	{cout<< q[i]<< ' ';
	}

	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文标题：归并排序—C++实现-创新互联
分享地址：http://mswzjz.cn/article/csigoc.html