堆排序
1、基本思路
1)最大堆（堆可以视为一棵完全二叉树）满足性质：根节点的值大于子节点。依据这一性质可以将数组重新排成一种最大堆（在树中从上到下从左到右依次为数组的各个元素）。
2）最大堆中，根节点的值总是该堆中最大的值，应此也是这个子数组的最大值，排序成功后其必然在子数组的末尾位置。交换最大堆得根节点和尾节点，除去这个元素之后的子数组也可以构成最大堆。迭代此过程这可以获得数组的最终排序。
伪代码：
heapsort(A)
build-max-heap(A)
for i=length[A] downto 2
exchange A[1],A[i]
heap-size[A] = heap-size[A] - 1
max-heapify(A,1)
build-max-heap(A)
heap-size[A] = length[A]
for i=floor(length[A]/2) downto 1
max-heapify(A,i)
max-heapify(A,i)
l=left(i)
r=right(i)
if l<=heap-size[A] and A[l]>A[i]
largest = l
else
largest = i
if r<=heap-size[A] and A[r]>A[largest]
largest = r
if largest != i
exchange A[i], A[largest]
max-heapify(A,largest)
parent(i)
return floor(i/2)
left(i)
return 2i
right(i)
return 2i+1
2、C++代码
#include<algorithm>
#include<iostream>
using namespace std;
//保证以i为根结点的子树具有最大堆性质
void max_heapify(int* A, int i,int heap_size)
{
int l = 2 * (i+1) - 1;//i节点的左节点索引
int r = 2 * (i+1) ;//i节点的右节点索引
int largest = 0;//记录最大值的索引
//在A[i],A[21],A[2i+1]中找出最大的值，记录其索引
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)
{
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
//在新更新的字节点处递归调用自身
max_heapify(A, largest,heap_size);
}
}
//构建最大堆
void build_max_heap(int* A, int length, int heap_size)
{
int len = length - 1;
//根据树的结构，推到后只需要处理倒数第二层之前的阶段就肯定可以完全构建好，即[1,...,floor(n / 2)]
for (int i = floor(len / 2); i >= 0; --i)
max_heapify(A, i,heap_size);
}
void heapsort(int* A, int length)
{
int heap_size = length;
build_max_heap(A,length,heap_size);
for (int i = length - 1; i > 0; --i)
{
//将剩余子树中最大的数（根节点）排至末尾
int temp = A[0];
A[0] = A[i];
A[i] = temp;
//减小heap_size，因为A[heap_size]之后的元素都排好了，每次A[0]都是最大的
heap_size = heap_size - 1;
//重排剩余的元素构成的树使其满足最大堆性质
max_heapify(A, 0, heap_size);
}
}
int main()
{
int A[5] = { 5,3,2,4,1 };
int length = 5;
heapsort(A, length);
return 0;
}
