首页 > 其他 > 详细

Iterative (non-recursive) Merge Sort

时间:2014-06-03 02:31:47      阅读:370      评论:0      收藏:0      [点我收藏+]

An iterative way of writing merge sort:

#include <iostream>
using namespace std;

void merge(int A[], int l, int r, int e, int B[]) {
	int i = l, j = r, k = l;
	while (i<r && j<e) {
		if (A[i] > A[j]) B[k++] = A[j++];
		else B[k++] = A[i++];
	}
	while (i < r) B[k++] = A[i++];
	while (j < e) B[k++] = A[j++];
}

void mergeSort(int A[], int n) {
	int *B = new int[n];
	for (int w=1; w<n; w<<=1) {
		for (int i=0; i<n; i+=(w<<1)) {
			merge(A, i, min(i+w, n), min(i+(w<<1), n), B);
		}
		for (int i=0; i<n; ++i) A[i] = B[i];
	}
	delete[] B;
}

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


Iterative (non-recursive) Merge Sort,布布扣,bubuko.com

Iterative (non-recursive) Merge Sort

原文:http://blog.csdn.net/jsc0218/article/details/27576405

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!