[结合插入排除的]归并排序(MergeInsertionMixSort) -- C++实现


实现代码

// MergeInsertionMixSort.h
#ifndef MERGEINSERTIONMIXSORT_H
#define MERGEINSERTIONMIXSORT_H

#include<iostream>
using namespace std;

#include "Component.h"

namespace jay{

	template< typename T >
	void MergeInsertionMixSort(T *input,T *input_buf ,int low_index,int high_index)
	{
		int nInsertSize = 7;
		
		// 如果当前分组小于7个元素就直接使用插入排序
		if (high_index <= (low_index + nInsertSize))
		{
			InsertionSortByIndex(input,low_index,high_index);
			return;
		}

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

		// 递归处理左半部份
		MergeInsertionMixSort(input,input_buf,low_index,nMid);
		// 递归处理右半部份
		MergeInsertionMixSort(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"
#include "MergeInsertionMixSort.h"
#include "MergeSortBottonToTop.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;
	MergeInsertionMixSort<int>(testarray,testarraybuf,0,iCount-1);
	timec.PrintTimeInfo();
	PrintArray<int>(testarray,iCount,"排序后:");

	delete []testarray;
	delete []testarraybuf;

	// 打印操作耗时


}

 

暂无评论

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