堆排序（原理加代码）

博客园他人教程：
https://www.cnblogs.com/chengxiao/p/6129630.html

C语言代码：

#include <stdio.h>

int count = 0;

void swap(int k[], int i, int j)
{
    
	int temp;

	temp = k[i];
	k[i] = k[j];
	k[j] = temp;
}

void HeapAdjust(int k[], int s, int n)
{
    
	int i, temp;

	temp = k[s];

	for( i=2*s; i <= n; i*=2 )
	{
    
		if( i < n && k[i] < k[i+1] )
		{
    
			i++;
		}

		if( temp >= k[i] )
		{
    
			break;
		}

		k[s] = k[i];
		s = i;
	}

	k[s] = temp;
}

void HeapSort(int k[], int n)
{
    
	int i;

	for( i=n/2; i > 0; i-- )
	{
    
		HeapAdjust(k, i, n);//从下往上，从左往右，将初始的无序序列构造大顶堆
	}

	for( i=n; i > 1; i-- )
	{
    
		swap(k, 1, i);//将堆顶和最后一个节点交换
		HeapAdjust(k, 1, i-1);//从上往下（已知根节点已发生变化），从左往右构造大顶堆
	}
}

int main()
{
    
	int i, a[10] = {
    -1, 5, 2, 6, 0, 3, 9, 1, 7, 4};//a[0]当作空位，根节点从a[1]开始，更容易分析代码

	HeapSort(a, 9);

	printf("排序后的结果是：");
	for( i=1; i < 10; i++ )
	{
    
		printf("%d", a[i]);
	}
	printf("\n\n");

	return 0;
}