基本思想：①把一个数组A构造成一个二叉最大堆， ②然后交换下标为0和下标为A-1的值，且每次heap_size - - ， ③然后再调整该堆为最大堆。最后循环执行②③，直至heap_size有效元素为1，堆排序算法结束。
二叉堆
为了更加清楚的了解堆排序的整个过程，我们先来介绍一下最大堆：
二叉堆可以分为两种形式：最大堆和最小堆。在这两种堆中，结点的值都要满足堆的性质，但一些细节定义则有所差异。在最大堆中，最大堆性质是指除了根以外的所有结点i都要满足：
A[ PARENT( i ) ] >= A[ i ]
也就是说，某个结点的值至多与其父节点一样大。因此，堆中的最大元素存放在根节点中；并且，在任一子树中，该子树所包含的所有结点的值都不大于该子树根节点的值。
最小堆的组织方式正好相反：最小堆性质是指除了跟以外的所有结点i都有：
A[ PARENT( i ) ] <= A( i )
最小堆中的最小元素存放在根节点中。
在堆排序中，我们使用的是正是最大堆。最小堆通常用于构造优先队列。
如下图所示：右边是一个数组A，左边就是由数组A构成的最大堆。如果树的根节点是A[1]，那么给定一个下标i，我们很容易计算得到它的父节点，左孩子和右孩子的下标：
PARENT( i )：
return i/2
LEFT( i )：
return 2i
RIGHT( i )：
return 2i+1
----------
//排序算法：堆排序
//时间：2018年1月13日
//时间复杂度：O(nlogn)
//空间复杂度：O(1)
//稳 定 性：不稳定
//by Ingran
----------
#include <iostream>
#include <iomanip>
#include <time.h>
void Swap(int a[], int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void MAX_HEAPIFY(int a[],int heap_size, int i)//调整最大堆
{
int l = 2 * i;
int r = 2 * i + 1;
int largest = 0;//保存(父节点，左子树，右子树)中的最大值
if (l <= heap_size && a[l] > a[i])
largest = l;
else
largest = i;
if (r <= heap_size && a[r] > a[largest])
largest = r;
if (largest != i)
{
Swap(a, i, largest);//交换a[i]与a[largeset]
MAX_HEAPIFY(a,heap_size,largest);
}
}
void BUILD_MAX_HEAP(int a[],int len)//构建最大堆
{
int heap_size = len;
for (int i = len / 2; i >= 0; i--)
{
MAX_HEAPIFY(a, heap_size, i);
}
}
void HEAP_SORT(int a[], int len)//堆排序
{
int heap_size = len;
BUILD_MAX_HEAP(a, len);
for (int i = len; i >= 1; i--)
{
Swap(a, i, 0);
heap_size = heap_size - 1;
MAX_HEAPIFY(a, heap_size, 0);
}
}
int main()
{
int n = 0;
int *p = nullptr;
srand((unsigned)time(NULL));
std::cout << "请输入随机数个数：" << std::endl;
std::cin >> n;
p = new int[n];
std::cout << "排序前：" << std::endl;
for (int i = 0; i < n; i++)
{
p[i] = rand() % 21;
std::cout << p[i] << " ";
if (i % 10 == 9 && i != 0)
std::cout << std::endl;
}
HEAP_SORT(p, n-1);
std::cout << std::endl << "排序后:" << std::endl;
for (int i = 0; i < n; i++)
{
std::cout << std::setw(2)<< p[i] << " ";
if (i % 10 == 9)
std::cout << std::endl;
}
system("pause");
return 0;
}