[自底向上的]归并排序(MergeSortBottomToTop) -- C++实现


实现代码

// MergeSortBottomToTop.h
#ifndef MERGESORTBOTTOMTOTOP_H
#define MERGESORTBOTTOMTOTOP_H

#include<iostream>
using namespace std;

#include "Component.h"

namespace jay{

	template< typename T >
	void MergeSortBottomToTop(T *input,T *input_buf ,int low_index,int high_index)
	{
		if (low_index >= high_index)
		{
			return;
		}

		// nCurrentSize为当前待归并的[每个]子数组的大小,每次归并2个子数组
		// 第一次归并的子数组其大小肯定为1,下一次翻倍
		int nCurrentSize = 1;

		// 当前归并的2子数组的低位索引
		int nCurrentLow = 0;

		for (; nCurrentSize <= high_index; nCurrentSize = nCurrentSize * 2)
		{
			// 合并2个子数组 所以下一次nCurrentLow的值变成nCurrentLow += 2 * nCurrentSize
			for (nCurrentLow = 0; nCurrentLow <= (high_index - nCurrentSize); 
				nCurrentLow += 2 * nCurrentSize )
			{
				int nlow = nCurrentLow;
				int nhigh = nlow + (2 * nCurrentSize - 1);
				if (nhigh >high_index )
					nhigh = high_index;
				
				int nMid = nlow + nCurrentSize -1;
				// int nMid = nlow + (nhigh - nlow) / 2; // error!!
				
				// 合并左右两部分
				Merge<T>(input,input_buf,nlow,nhigh,nMid);
			} 
		}
		
	}

};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>

#include <iostream>
using namespace std;

#include "Component.h"
#include "SelectSort.h"
#include "InsertionSort.h"
#include "ShellSort.h"
#include "MergeSort.h"
#include "MergeInsertionMixSort.h"
#include "MergeSortBottomToTop.h"

using namespace jay;


int main(int argc, char* argv[])
{
	int iElentmentsCunt(0) ;
	cin>>iElentmentsCunt;
	int *testarray = new int[iElentmentsCunt];
	int *testarraybuf = new int[iElentmentsCunt];

	int iCount = 0;
	int p;


	while(cin>>p)
	{
		testarray[iCount] = p;
		iCount++;
	}

	PrintArray<int>(testarray,iCount,"排序前:");
	TimeCalculator timec;
	MergeSort<int>(testarray,testarraybuf,0,iCount-1);
	timec.PrintTimeInfo();
	PrintArray<int>(testarray,iCount,"排序后:");

	cout << "是否已序? " << isSortedAndPrintInfo<int>(testarray,0,iCount-1) << endl;

	delete []testarray;
	delete []testarraybuf;

	// 打印操作耗时
}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。