堆排序

堆排序基于二叉树的结构，根节点比叶子节点都大或者比叶子结点都小，通过这种结构在最上面的根节点就是最大或者最小的元素。
对输入的任意一个数字序列，先按顺序形成一个完全二叉树；
对没有叶子的就不用管，对有叶子结点的根节点要进行调整，把叶子结点和根节点按大小换一换位置，且从下往上依次调整。
但要注意的是，上面调整过换下来的结点会对已经调整好的结点造成影响，对下面的结点还要重新调整。但根据二叉的特点，时间复杂度是nlog（n)。
第一遍调整出一个最大或者最小的与最后面互换。之后的n-1遍就没有这么复杂，只要对新的根节点调整即可，时间复杂度是log（n）。

#include<stdio.h>
#include<stdbool.h>
#define SIZE 100
typedef int ElemType;

typedef struct SqList {
	ElemType a[SIZE];
	int length;
}SqList;
void HeapAdjust(SqList& L, int s, int m)
{
	int rc = L.a[s];
	for (int j = s*2; j <= m; j *= 2)
	{
		if (j < m && L.a[j] < L.a[j + 1])j++;
		if (L.a[j] <= rc)break;
		L.a[s] = L.a[j]; s = j;
	}
	L.a[s] = rc;
}

void HeapSort(SqList& L)
{
	for (int i = L.length / 2; i >=1; i--)HeapAdjust(L, i, L.length);
	for (int i = L.length; i >=1 ; i--)
	{
		int temp = L.a[1];
		L.a[1] = L.a[i];
		L.a[i] = temp;
		HeapAdjust(L, 1, i-1);
	}
}

堆排序

原文：https://www.cnblogs.com/tzp-empty-hya/p/14984210.html