bottomupsort.cpp

自底向上排序

// BottomupSort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h" 

int Comparetimes = 0;
int SetValtimes = 0;

void Merge(int A[],int p,int q,int r);
void BottomupSort(int A[],int len);


int main(int argc, char* argv[])
{
	int A[256];
	int len = 0,tmp = 0, k = 0;
	cout<<"输入数组A:"<<endl;
	while(tmp != -1)
	{
		
		cin>>tmp;
		if (tmp==-1) break;
		cout<<"Next:"<<endl;
		
		A[k] = tmp;
		k++;
		
	}
	len = k ;
	cout<<"数组A: ";
	k = 0;
	while(k != len-1)
	{
		cout<<A[k]<<",";
		k++;
	}
	cout<<A[k];
	cout<<endl;
	cout<<"长度:"<<len<<endl;
	///////////////////////////////////////
    //对数组进行排序
	///////////////////////////////////////
	BottomupSort(A,len);

	cout<<"排序后数组A: ";
	k = 0;
	while(k != len-1)
	{
		cout<<A[k]<<",";
		k++;
	}
	cout<<A[k];
	cout<<endl;
	cout<<"长度:"<<len<<endl;
	///////////////////////////////////////
	cout<<"元素比较次数: "<<Comparetimes<<endl;
	cout<<"元素赋值次数: "<<SetValtimes<<endl;

	return 0;
}

void BottomupSort(int A[],int len)
{

	int i, s = 1;
	while(s < len)
	{
		i = 0;
		while (i+2*s <= len)
		{
			Merge(A,i,i+s-1,i+2*s-1);
			i = i+2*s;
		}
		if (i+s <= len-1) Merge(A,i,i+s-1,len-1);
		s = 2*s;
	}


}

void Merge(int A[],int p,int q,int r)
{

	int s = p, t = q+1;
	int tmp = 0;
	int B[256];
	int k = 0;
	while (s <= q && t <= r)
	{
		Comparetimes++;
		if (A[s] < A[t])
		{
			SetValtimes++;
			B[k] = A[s];
			s++;
		}
		else 
		{
			SetValtimes++;
			B[k] = A[t];
			t++;
		}
		k++;

	}
	if (s == q+1)
	{
		for (int j=t;j<=r;j++)
		{
			SetValtimes++;
			B[k] = A[j];
			k++;
		}
	}
	else 
	{
		for (int j=s;j<=q;j++)
		{
			SetValtimes++;
			B[k] = A[j];
			k++;
		}
	}
	k = 0;
	for (int j=p;j<=r;j++)
	{
		SetValtimes++;
		A[j] = B[k];
		k++;
	}


}