选择排序：
选择排序：每一趟在待选择元素中选取关键字最小（或最大）的元素加入有序子序列
难理解！！
若n个关键字序列L[1...n] 满足下面某一条性质，则称为堆（Heap）：
大根堆：完全二叉树中，根≥左、右
相应的小根堆，就是根节点小于左右两边的结点。
堆顶元素关键字最大
根≥左、右
思路：把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整
在顺序存储的完全二叉树中，非终端节点n/2
检查当前节点是否满足跟≥左、右
若不满足，将当前结点与更大的一个孩子互换。
更小的元素“下坠”可能导致下一层的子树不符合大根堆的要求
//建立大根堆
void BildMaxHeap(int A[],int len){
for(int i=len/2;i>0;i--) //从后往前调整所有非终端节点
HeadAdjust(A,i,len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
A[0] = A[k]; //A[0]暂存子树的根节点
for(int i=2*k;i<=len;i*=2){ //沿key较大的子节点向下筛选
if(i<len&&A[i]<A[i+1])
i++; //取key较大的子节点的下标
if(A[0]>=A[i]) break; //筛选结束
else{
A[k]=A[i]; //将A[i]调整到双亲结点
k=1; //修改k值，以便
}
}
A[k]=A[0]; //被筛选结点的
}
选择排序：每一趟在待排序元素中选取关键字最大的元素加入有序子序列
堆排序：每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素进行交换）
并将待排序元素序列再此调整为大根堆（小元素不断“下坠”）
注意：基于“大根堆”的堆排序得到“递增序列”
//建立大根堆
void BildMaxHeap(int A[],int len){
for(int i=len/2;i>0;i--) //从后往前调整所有非终端节点
HeadAdjust(A,i,len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
A[0] = A[k]; //A[0]暂存子树的根节点
for(int i=2*k;i<=len;i*=2){ //沿key较大的子节点向下筛选
if(i<len&&A[i]<A[i+1])
i++; //取key较大的子节点的下标
if(A[0]>=A[i]) break; //筛选结束
else{
A[k]=A[i]; //将A[i]调整到双亲结点
k=1; //修改k值，以便
}
}
A[k]=A[0]; //被筛选结点的
}
//堆排序的完整逻辑
void HeapSort(int A[],int len){
BuildMaxHeap(A,len); //初始建堆
for(int i=len;i>1;i--){ //n-1趟的交换和建堆过程
swap(A[i],A[1]); //堆顶元素和堆底元素交换
HeadAdjust(A,1,i-1); //把剩余的待排序元素整理成堆
}
}
i指向当前待排序元素序列中的最后一个（堆底元素）
下方有两个孩子，则“下坠“一层，需要对比关键字两次
下方只有一个孩子，则”下坠“一层，对比关键字一次
结论：一个结点，每”下坠“一层，最多只需要对比关键字2次
若树高为h，某节点在第1层，则将这个结点向下调整最多只需要”下坠“h-i层，关键字对比次数不超过2(h-i)
第i层最多有2^i-1个结点，而只有第1~(h-1)层的结点才有可能需要”下坠“调整
将整棵树调整为大根堆，关键字对比次数不超过
差比数列求和（错位相减法）
建堆的过程中，关键字对比次数不超过4n，建堆时间复杂度=O(n)
共n-1趟
堆排序是不稳定的
顺便考了完全二叉树和顺序存储
原文：https://www.cnblogs.com/jev-0987/p/13322172.html