heapsort.cpp

堆排序算法

#include <iostream.h>
#include <stdlib.h>
#include "Heap.h"
#define SIZE_SORT 200

bool Heap::Insert(Type item)
{
	//insert item
	int i = ++Nel;
	if (i == MaxSize)
	{
		cout<<"Heap size exceeded"<<endl;
		return false;
	}
	while ((i > 1) && ( array[i/2] < item ))
	{
		array[i] = array[i / 2];
		i /= 2;
	}

	array[i] = item;
	return true;
}



void Heap::Adjust(Type a[],int i,int n)
{
	int j = 2 * i;
	Type item = a[i];
	while (j <= n)
	{
		if ((j < n) && (a[j] < a[j+1] ) )
		{
			j++;
		}	
		if (item >= a[j])
		{
			break;
		}
		a[j/2] = a[j];
		j *= 2;
	}
	a[j/2] = item;
}

bool Heap::DelMax(Type & item)
{
	if (!Nel)
	{
		cout<<"heap is empty"<<endl;
		return false;
	}
	item = array[1];
	array[1] = array[Nel--];
	Adjust(array,1,Nel);
	return true;
}


void Sort(Type a[],int n)//堆排序
{
	Heap heap(SIZE_SORT);
	for (int i = 1;i <= n;++i )
	{
		heap.Insert(a[i]);
	}
	Type x;
	for( i = 1;i <= n;++i)
	{
		heap.DelMax(x);
		a[n-i+1] = x;
	}
}

void main()
{
	Type data[21];
	for (int i = 1;i <= 20;++i)
	{
		data[i] = rand() % 100;//random()
	}
	for (i = 1;i <= 20;++i)
	{
		cout<<data[i]<<" ";
	}
	cout<<endl;
	Sort(data,20);
	for (i = 1;i <= 20;++i)
	{
		cout<<data[i]<<" ";
	}
	cout<<endl;
	return;
}