堆排序

参考：
https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F/2840151

http://cuijiahua.com/blog/2018/01/algorithm_6.html

一、原理

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即$A_{[PARENT_{[i]}]} >= A_{[i]}$。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

堆是一棵顺序存储的完全二叉树。

其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于n个元素的序列${R_{0}, R_{1}, … , R_{n}}$当且仅当满足下列关系之一时，称之为堆：
$R_{i}<=R_{2i+1}$ 且 $R_{i}<=R_{2i+2}$ (小根堆)
$R_{i}>=R_{2i+1}$ 且 $R_{i}>=R_{2i+2}$ (大根堆)
其中i=1,2,…,n/2向下取整；

二、步骤

设当前元素在数组中以R[i]表示，那么，

(1) 它的左孩子结点是：R[2*i+1];

(2) 它的右孩子结点是：R[2*i+2];

(3) 它的父结点是：R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；
然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
如此反复，直到交换了R[0]和R[1]为止。

以上思想可归纳为两个操作：

（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。

三、算法实现

C语言

#include <stdio.h>

void adjustHeap(int param1, int j, int inNums[]);
void  HeapSort(int nums, int inNums[]);
//大根堆进行调整
void adjustHeap(int param1, int j, int inNums[])
{
	int temp = inNums[param1];
	for (int k = param1 * 2 + 1; k<j; k = k * 2 + 1)
	{
		//如果右边值大于左边值，指向右边
		if (k + 1<j && inNums[k]< inNums[k + 1])
		{
			k++;
		}
		//如果子节点大于父节点，将子节点值赋给父节点,并以新的子节点作为父节点（不用进行交换）
		if (inNums[k]>temp)
		{
			inNums[param1] = inNums[k];
			param1 = k;
		}
		else
			break;
	}
	//put the value in the final position
	inNums[param1] = temp;
}
//堆排序主要算法
void HeapSort( int inNums[],int nums)
{
	int i, j;
	//1.构建大顶堆
	for (i = nums / 2 - 1; i >= 0; i--)
	{
		//put the value in the final position
		adjustHeap(i, nums, inNums);
	}
	//2.调整堆结构+交换堆顶元素与末尾元素
	for (j = nums - 1; j>0; j--)
	{
		//堆顶元素和末尾元素进行交换
		int temp = inNums[0];
		inNums[0] = inNums[j];
		inNums[j] = temp;

		adjustHeap(0, j, inNums);//重新对堆进行调整

		printf("第%d次循环：\t", nums-j);
		for (i = 0; i < nums; i++)
		{
			printf("%d\t", inNums[i]);
		}
		printf("\n");
	}


}

int main()
{
	int number[] = { 0, 10, 1, 2, 8, 5, 9, 7, 3, 4, 6 };
	int i;
	int n = sizeof(number) / sizeof(number[0]);
	printf("原始数据：\n");
	for (i = 0; i < n; i++)
	{
		printf("%d\t", number[i]);
	}
	printf("\n\n");

	HeapSort(number, n);
	printf("\n返回结果：\n");
	for (i = 0; i < n; i++)
	{
		printf("%d\t", number[i]);
	}
	printf("\n");
}

堆排序

一、原理

二、步骤

三、算法实现

C语言

运行结果