前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构:归并排序(自顶向下和自底向上)递归和非递归

数据结构:归并排序(自顶向下和自底向上)递归和非递归

作者头像
lexingsen
发布2022-02-24 19:09:02
3070
发布2022-02-24 19:09:02
举报
文章被收录于专栏:乐行僧的博客乐行僧的博客

1.自顶向下

代码语言:javascript
复制
#include <iostream>
using namespace std;

//合并两个有序数组的操作
//索引m是第二区间的左边界
void merge(int *a, int l, int m, int r) {
	int LEFT_SZIE  = m - l;
	int RIGHT_SIZE = r - m + 1;
	int *left  = new int[LEFT_SIZE];
	int *right = new int[RIGHT_SIZE];
	for(int i=l; i<m; ++i) left[i-l] = a[i];
	for(int i=m; i<=r; ++i) right[i-m] = a[i];
	int i=0, j=0, k=l;
	while(i < LEFT_SZIE && j < RIGHT_SIZE) {
		if(left[i] < right[j]) a[k ++] = left[i ++];
		ekse a[k ++] = right[j ++];
	}
	while(i < LEFT_SIZE)  a[k ++] = left[i ++];
	while(j < RIGHT_SIZE) a[k ++] = right[j ++];


	delete[] left;
	delete[] right;
}

void _mergeSort(int *a, int l, int r) {
	if(l >= r) return;
	int m = (r - l) / 2 + l;
	_mergeSort(a, l, m);
	_mergeSort(a, m+1, r);
	merge(a, l, m+1, r);
}


void mergeSort(int *a, int n) {
	_mergeSort(a, 0, n-1);
}

int main() {
    int a[] = {4, 1, 8, 0, 3, 5, 7, 6, 2};
    int n = sizeof a/sizeof(int);

    cout << n << endl;

    mergeSort(a, n);
    for_each(a, a+n, [](int a) {cout << a << " ";}); cout << endl;
    return 0;
}

2.自底向上

代码语言:javascript
复制
//merge操作和上边是一样的
//这种实现方式参考算法四的实现
void _mergeSortBU(int *a, int n) {
	for(int sz=1; sz<n; sz+=sz) 
		//对a[i...i+sz-1]和a[i+sz....i+2*sz-1]进行归并
        /*(1)为了保证由两个归并段i+sz < n
          (2)为了保证不越界 min(i+2*sz-1, n-1)*/
		for(int i=0; i+sz<n; i+=sz+sz) 
			merge(a, i, i+sz, min(i+sz+sz-1, n-1));
}

void mergeSortBU(int *a, int n) {
	_mergeSortBU(a, n);
}

int main() {
    int a[] = {4, 1, 8, 0, 3, 5, 7, 6, 2};
    int n = sizeof a/sizeof(int);

    cout << n << endl;

    mergeSortBU(a, n);
    for_each(a, a+n, [](int a) {cout << a << " ";}); cout << endl;
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档