学步园

// HeapSort.cpp : 定义控制台应用程序的入口点。
//
/*
堆排序：
堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
（1）用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，
由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。

平均、最小、最坏时间复杂度：O(nlbn)
稳定性：不稳定。
*/

#include "stdafx.h"
#include <iostream>
#include <iomanip>
using namespace std;

//调整为大根堆
void HeapAdjust(int *a,int i,int length)
{
	int Child,Temp;
	for( Temp = a[i];2*i+1<length;i=Child )  //一直循环其孩子节点
	{
		Child = 2*i+1;
		if( Child < length-1&&a[Child+1]>a[Child] )//将Child指向数最大的孩子节点
			++Child;
		if( Temp < a[Child] )            //找到最大的孩子节点进行交换
		{
			a[i] = a[Child];
			a[Child] = Temp;
		}
		else                           //如果没有找到，说明本节点一下的子节点都满足堆的性质，不需要调整了。
			break;
	}
}

void HeapSort(int *a,int length)
{
	int temp,i;
	for(i = length/2-1;i>=0;--i)
	{
		HeapAdjust(a,i,length);
	}
	for(i = length-1;i>0;--i)
	{
		temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		HeapAdjust(a,0,i);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int a[] = {20,5,22,46,78,10,33,4};
	HeapSort(a,8);
	for(int i = 0; i<8; i++)
	{
		cout<<a[i]<<setw(3);
	}
	return 0;
}