学步园

堆排序源代码

// 堆排序
// 2014-2-27
#include <iostream>
using namespace std;

void MaintainHeap(int* array, int i, int n); //用循环实现堆的维护
void RecursionHeap(int* array, int i, int n);//用递归实现堆的维护
void Exchange(int* a, int* b);
void BuildHeap(int* array, int n);
void HeapSort(int* array, int n);

int main()
{
	int array[10];
	for (int i = 0; i < 10; ++ i)
		cin >> array[i];
	HeapSort(array, 10);
 	for (i = 0; i < 10; ++ i)
 		cout << array[i] << " ";
 	cout << endl;
	return 0;
}

void MaintainHeap(int* array, int i, int n)
{
	for (int j = i; j < n; )
	{
		int large = j;
		if (2 * j + 1 < n && array[2 * j + 1] > array[j])
			large = 2 * j + 1;
		if (2 * j + 2 < n && array[2 * j + 2] > array[large])
			large = 2 * j + 2;
		if (large != j)
		{
			Exchange(&array[j], &array[large]);
			j = large;
		}
		else
			break;
	}
}

void RecursionHeap(int* array, int i, int n)
{
	int large;
	if (2 * i + 1 < n && array[2 * i + 1] > array[i])
		large = 2 * i + 1;
	else 
		large = i;
	if (2 * i + 2 < n && array[2 * i + 2] > array[large])
		large = 2 * i + 2;
	if (large != i)
	{
		Exchange(&array[i], &array[large]);
		RecursionHeap(array, large, n);
	}
}

void BuildHeap(int* array, int n)
{
	for (int i = (n - 2) / 2; i >= 0; -- i)
		MaintainHeap(array, i, n);
}

void HeapSort(int* array, int n)
{
	BuildHeap(array, n);
	for (int i = n - 1; i > 0; -- i)
	{
		Exchange(&array[0], &array[i]);
		RecursionHeap(array, 0, i);
	}
}

void Exchange(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}