bottomupsort.cpp

来自「用C++6.0编写」· C++ 代码 · 共 80 行

#include "stdafx.h"
#include<iostream>
#include "BottomUpSort.h"
using namespace std;
BottomUpSort::BottomUpSort(int bus_Size)
{
	reset(bus_Size);
}
void BottomUpSort::reset(int bus_Size)
{
	Array1=new int[bus_Size];
	busSize=bus_Size;
}
void BottomUpSort::createArrayTemp(int size)
{
	arraytemp=new(int [size+1]);
}
void BottomUpSort::merge(int p,int q,int r)
{
	createArrayTemp(r);
	int s,t,k;
	s=p;
	t=q+1;
	k=p;
	while((s<=q)&&(t<=r))
	{
		if(Array1[s]<=Array1[t])
		{
			arraytemp[k]=Array1[s];
			s++;
		}
		else
		{
			arraytemp[k]=Array1[t];
			t++;
		}
			k++;
	}
	if(s==q+1)
	{
		for(int m=k;m<=r;m++)
		{
			arraytemp[m]=Array1[t];
			t++;
		}
	}
	else
	{
		for(int m=k;m<=r;m++)
		{
			arraytemp[m]=Array1[s];
			s++;
		}
	}
	for(int m=p;m<=r;m++)
	Array1[m]=arraytemp[m];
	delete[]arraytemp;
}
void BottomUpSort::bottomUp()
{
	int t=1;
	int s,i;
	while(t<busSize-1)
	{
		s=t;
		t=2*s;
		i=0;
		while(i+t<=busSize-1)
		{
			merge(i,i+s-1,i+t-1);
			i=i+t;
		}
		if(i+s<busSize-1)merge(i,i+s-1,busSize-1);
	}
}
void BottomUpSort::output()
{
	cout<<"长度为"<<busSize<<"的数组";
	cout<<"执行自底向上合并排序所需的时间为："<<costTime<<" ms"<<endl;
}