2021-05-19

最新推荐文章于 2025-05-30 22:14:47 发布

天生傲骨！

最新推荐文章于 2025-05-30 22:14:47 发布

阅读量70

点赞数

分类专栏：排序算法文章标签：分治算法排序算法算法

本文链接：https://blog.csdn.net/qq_52588168/article/details/117046810

版权

排序算法专栏收录该内容

3 篇文章

订阅专栏

二路归并排序算法：

利用分治思想先把要排序的数组进行划分像二分查找一样从中点处开始划分r=(p+q)/2；

然后递归划分mergesort（a,p,r）;mergesort(a,r+1,q);

最后再递归合并

注意：合并的时候要新建立两个辅助数组b[]和c[]，然后把b和c中的元素按照要求的顺序重新写入a中

具体过程：

代码实现：

#include<iostream>
#include<bits/stdc++.h>
#include<vector>
using namespace std;

//对划分的数组进行合并
void merge(int a[], int p, int r, int q) {
	int n1 = r - p + 1;
	int n2 = q - r;
	vector<int>b(n1 + 1);
	vector<int>c(n2 + 1);
	for (int i = 0; i < n1; ++i) {
		b[i] = a[i + p];
	}
	for (int i = 0; i < n2; ++i) {
		c[i] = a[i + r + 1];
	}
	int i = 0, j = 0, k = p;
	while (i < n1 && j < n2) {
		if (b[i] <= c[j]) {
			a[k++] = b[i++];
		}
		else {
			a[k++] = c[j++];
		}
	}
	while (i < n1) {
		a[k++] = b[i++];
	}
	while (j < n2) {
		a[k++] = c[j++];
	}
}
//利用分治思想对数组划分
void mergesort(int a[], int p, int q) {
	if (p < q) {
		int r = (p + q) / 2;
		mergesort(a, p, r);
		mergesort(a, r + 1, q);
		merge(a, p, r, q);
	}
}


int main() {
	int a[6] = { 5,4,3,2,1,0 };
	mergesort(a, 0, 5);
	for (int i = 0; i < 6; ++i) {
		cout << a[i] << " ";
	}
	return 0;
}