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 <len)  {  temp[temppos++] = arr[l1++];  }  //用temp覆盖arr  for (int i = 0; i < len ; ++i)  {  arr[i] = temp[i];  } // free(temp); } void MergeSort(int *arr, int len) {  for (int i = 1; i < len; i *= 2)  {  Merger(arr, len, i);  } } void show(int *arr, int len) {  for (int i = 0; i < len; ++i)  {  cout << arr[i] << " ";  } } int main() {  int array[] = { 12, 51, 1, 36, 98, 21, 38, 47 };  int len = sizeof(array) / sizeof(array[0]);  MergeSort(array, len);  show(array, len);  system("pause");  return 0; }

PS:二路合并排序算法

#include<iostream> 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++如何实现二路归并排序这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！