heapsort.cpp

算法中的堆排序算法的实现

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

#include "stdafx.h"
#include <iostream.h>

int H[256];

void SiftUp(int H[], int i, int n);
void SiftDown(int H[],int i,int n);
void HeapSort(int H[],int n);
void InputArray(int A[],int &len);
void OutputArray(int A[],int n);
void MakeHeap(int H[],int n);

int main(int argc, char* argv[])
{
	cout<<"***HeapSort***\n输入数组H:\n";
	int n = 0;	
	InputArray(H,n);
	OutputArray(H,n);
	cout<<"MakeHeap..."<<endl;
	MakeHeap(H,n);
	cout<<"+OK!\n";
	OutputArray(H,n);
	cout<<"HeapSort...\n";	
	HeapSort(H,n);
	cout<<"+OK!"<<endl;
	OutputArray(H,n);
	return 0;
}


void SiftUp(int H[], int i, int n)
{
	bool done = false;
	int tmp = 0;

	if (i == 1) return ;
	while( i!=1&&!done)
	{
		if (H[i]>H[i/2])
		{
			tmp = H[i];
			H[i] = H[i/2];
			H[i/2] = tmp;
		}
		else done = true;
		i = i/2;

	}
}
void SiftDown(int H[],int i,int n)
{
	bool done = false;
	int  tmp = 0;
	
	if (2*i > n) return ;
	while(2*i<=n&&!done)////
	{
		i = 2*i;
		if (i+1<=n&&H[i+1]>H[i]) i++;
		if (H[i/2]<H[i])
		{
			tmp = H[i];
			H[i] = H[i/2];
			H[i/2] = tmp;
		}
		else done = true;

	}

}
void MakeHeap(int H[],int n)//将数组H[1...n]转换为堆
{
	int i = 0;
	for (i=n/2;i>=1;i--)
		SiftDown(H,i,n);

}
void HeapSort(int H[],int n)
{
	int tmp = 0;
	for(int j = n;j>=2;j--)
	{	
		tmp = H[1];
		H[1] = H[j];
		H[j] = tmp;
		SiftDown(H,1,j-1);
	}
}
void InputArray(int A[],int &len)
{
	int tmp = 0;
	int k = 1;
	A[0] = -1;
	while(tmp != -1)
	{
		
		cin>>tmp;
		if (tmp==-1) break;
		cout<<"Next:"<<endl;
		
		A[k] = tmp;
		k++;
		
	}
	len = k - 1;
}
void OutputArray(int A[],int n)
{
	cout<<"数组A: ";
	int	k = 1;
	while(k != n)
	{
		cout<<A[k]<<",";
		k++;
	}
	cout<<A[k];
	cout<<endl;
	cout<<"长度:"<<n<<endl;
}