1，定义
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序；
简单的说，堆是一种完全二叉树，根据父子节点之间的大小关系的不同还可以细分为「大顶堆」和「小顶堆」。大顶堆是指任一节点的值都大于或等于其左右孩子的值，小顶堆是指任一节点的值都小于或等于其左右孩子的值。下图分别是大顶堆和小顶堆的结构。
我们以大顶堆为例，演示一下堆排序过程。
现在我们有一个待排序数组[2,7,4,3,1,9,5]，初始状态是这样的：
2,排序过程原理
?
找出最大数值然后放到末尾，次末尾，依次排放。
3，代码实现
C++代码实现如下：
// HeapSort.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
//测试数组 正确顺序维 2，3,7,12,15,31,34，45,54,64,86
int data[] = { 12,45,2,64,54,31,86,4243,5,242,2342,245,34,15,3,7 };
int datacount = 16;
void OnceSort(int data[], int count) {
for (int i = count / 2 - 1; i >= 0; i--)
{
int temp = 0;
if (data[i]>data[2 * i+1]) {
temp = data[i];
data[i] = data[2 * i+1];
data[2 * i+1] = temp;
}
if (data[i]>data[2 * i + 2]) {
temp = data[i];
data[i] = data[2 * i + 2];
data[2 * i + 2] = temp;
}
}
}
void HeapSort1(int data[], int count){
for (int i = count-1; i > 0;i--) {
OnceSort(data, i);
int temp = 0;
temp = data[i];
data[i] = data[0];
data[0] = temp;
}
}
int main()
{
std::cout << "原始数据 " << " ";
for (int i = 0; i <datacount; i++) {
std::cout << data[i] << " ";
}
std::cout << " " << std::endl;
HeapSort1(data, datacount);
std::cout << "排序数据 " << " ";
for (int i = 0; i <16; i++) {
std::cout << data[i] << " ";
}
std::cout << " " << std::endl;
system("echo 按回车继续...&pause>nul");
return 0;
}
运行结果如下：
?
?4，时间复杂度和空间负责度
? 时间负责度 O(nlogn)，
? 空间复杂度 O(1)
5，是否稳定、
? 不稳定
