堆排序
大根堆定义：根节点大于左右子节点
基本原理：堆排序是一树形选择排序。特点是：在排序过程中，将数组看成是一棵完全二叉树的顺序存储结构（如下图所示），利用完全二叉树中根结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录
根据完全二叉树的性质有
如果按照下标从0开始，如果该节点有左孩子节点或者右孩子节点
那么就有左孩子节点下标 = 2*i+1右孩子节点 = 2*i+2
时间复杂度：O(N*logN)
稳定性：不稳定
注意事项：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的排序
排序流程：
我们先构建一个大堆，第一次构建的时候 我们需要从底往上构建（简单一点）
后面每次只是需要对堆进行调整即可（从上往下 ）
public class HeapSelectSort {
public static void main(String[] args) {
int[] array = { 19, 8, 27, 6, 315, 14, 99 };
firstBuildMaxHeap(array);
for(int i=array.length-1;i>=0;i--)
{
exchange(array,0,i);
adjustMaxHeap(array, i, 0);
}
for (int i : array) {
System.out.print(" "+i);
}
}
//第一次构建大根堆 从下往上构建 会更简单一点
private static void firstBuildMaxHeap(int[] array) {
int half = (array.length-1)>>1;
for(int i=half-1;i>=0;i--)
{
adjustMaxHeap(array,array.length,i);
}
}
//调整堆
private static void adjustMaxHeap(int[] a, int length, int i) {
int left = 2*i+1; //左节点下标
int right = 2*i+2;//右节点下标
int large = i;
if(left<length && a[left]>a[i])
{
large = left;
}
if(right<length && a[right] > a[large] )
{
large = right;
}
//如果large不是当前的下标
if(large!=i)
{
exchange(a,large,i);
adjustMaxHeap(a,length,large);
}
}
private static void exchange(int[] a, int bigger, int i) {
int temp = a[bigger];
a[bigger] = a[i];
a[i] = temp;
}
}