排序算法堆排序

堆排序（Heap Sort）
堆是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆，或者每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。
堆排序的基本思想是，将待排序的序列构成一个大顶堆。此时整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其余堆数组的末尾就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。

若array[0，…，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：

任意一节点指针 i：父节点：i==0 ? null : (i-1)/2

左孩子：2*i + 1

右孩子：2*i + 2

最好情况o(nlogn)

最坏情况o(nlogn)

性能高于希尔排序，并不稳定。

public static void heapSort(int[] array) {  
        if (array == null || array.length <= 1) {  
            return;  
        }  
        headHeap(array);//先将原始数据构造成大顶堆  
        for (int i = array.length - 1; i >= 1; i--) {  
            swap(array, i, 0);//根节点和最后节点交换数据  
            sortHeap(array, i, 0);//重新构造大顶堆  
        }  
    }

//  
  /** 
   * 构建最大堆 
   * 在构建堆的过程中，我们是从最下层最右边的非终端节点开始构建，将它与 
   * 其孩子进行比较和若有必要的交换 
   */  
  static void headHeap(int[] array) {  
  
      if (array != null && array.length > 0) {  
          for (int i = (array.length - 1) / 2; i >= 0; i--) {//找出存在孩子节点的节点  
              sortHeap(array, array.length, i);  
          }  
      }  
  }```

static void sortHeap(int[] array, int n, int i) {
if (array != null && array.length > 0) {
int child = 2 * i + 1;//找出子节点
while (child < n) {//循环比较下一层节点
if (child + 1 < n && array[child + 1] > array[child]) {//存在右节点 右节点比左节点大
child = child + 1;
}
if (array[child] > array[i]) {//最大子节点与根节点比较
swap(array, child, i);
i = child;//设置最大节点 进行下一次比较
child = 2 * child + 1;//对比下一个节点
} else {//比孩子节点都大 不用继续 因为堆是底部往上构建的 比孩子大 就不用往下继续比
break;
}
}
}
}```

/** 
 * 将数组的2个位置交换 
 */  
static void swap(int[] array, int i, int j) {  
    if (array != null && array.length > 0) {  
        if (i >= 0 && j >= 0 && i <= array.length && j <= array.length) {  
            int temp = array[i];  
            array[i] = array[j];  
            array[j] = temp;  
        }  
    }  
}```