[自顶向下的]归并排序(MergeSort) -- C++实现


实现代码

// MergeSort.h
#ifndef MERGESORT_H
#define MERGESORT_H

#include<iostream>
using namespace std;

#include "Component.h"

namespace jay{

	template< typename T >
	void Merge(T *input,T *input_buf ,int low_index,int high_index,int mid_index)
	{
		for (int i = low_index; i <= high_index; i++) 
		{
			input_buf[i] = input[i]; 
		}

		int i = low_index;
		int j = mid_index + 1;
		for (int k = low_index; k <= high_index; k++) 
		{
			// 左部分的数据已经归并完毕,将右部分未归并的数据数据归并入数组input
			if(i > mid_index)              
				input[k] = input_buf[j++]; 
			// 右部分的数据已经归并完毕,将左部分未归并的数据数据归并入数组input
			else if (j > high_index)               
				input[k] = input_buf[i++]; 
			// 比较左右部分未处理的元素,将小的元素放入input[k],然后对应的位置+1,指向下一元素
			else if (input_buf[j] < input_buf[i])
				input[k] = input_buf[j++];
			else                           
				input[k] = input_buf[i++];
		}
	}

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

		int nMid = low_index + (high_index - low_index) / 2;

		// 递归处理左半部份
		MergeSort(input,input_buf,low_index,nMid);
		// 递归处理右半部份
		MergeSort(input,input_buf,nMid+1,high_index);
        
		// 数组已序
		if (input[nMid] <= input[nMid+1])
		{
			return;
		}

		// 合并左右两部分
		Merge<T>(input,input_buf,low_index,high_index,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"
using namespace jay;


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

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

	PrintArray<int>(testarray,iCount,"排序前:");
	TimeCalculator timec;
	MergeSort<int>(testarray,testarrayout,0,iCount-1);
	// 打印操作耗时
	timec.PrintTimeInfo();
	PrintArray<int>(testarray,iCount,"排序后:");

	delete []testarray;
	delete []testarrayout;

}

 

暂无评论

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