堆排序实现：
我们利用最大堆来实现排序，先了解下什么是最大堆呢，看图就明白了：
最大堆：所有根节点都必须大于其孩子。
- 那么对于一个普通的数组，我们要怎么让其变成最大堆呢，比如：
先看看怎么对一颗子树进行最大堆化，其实现代码为：
/**
* 最大堆化数组arr[index]为根的子树
* @param arr 对应数组
* @param index 根索引， 0 ～ arr.length－1
* @param lastIndex 比较操作的最大索引
*/
private static void maxHeapify(int arr[], int index, int lastIndex){
int leftChildIndex = left(index);
int rightChildIndex = right(index);
int biggest = index;
// 若果左边的孩子更大
if ((leftChildIndex <= lastIndex)
&& arr[index] < arr[leftChildIndex]){
biggest = leftChildIndex;
}
// 若右边的孩子还更大
if ((rightChildIndex <= lastIndex)
&& arr[biggest] < arr[rightChildIndex]){
biggest = rightChildIndex;
}
// 需要进行调整
if (biggest != index){
int temp = arr[biggest];
arr[biggest] = arr[index];
arr[index] = temp;
// 递归最大堆化子树
maxHeapify(arr, biggest, lastIndex);
}
}
// 获取左孩子索引
private static int left(int index) {
return 2*index+1;
}
// 获取右孩子索引
private static int right(int index) {
return 2*index+2;
}上面是对以index为根的子树进行最大堆化，那么要怎么对整个数组最大堆化呢，请看：
/**
* 对整个数组进行最大堆化:
* 可对每个非叶子节点出发进行最大堆化，
* 注意叶子节点索引为: [(arr.length)/2，+1, +2...n]，我们没必要对它们进行最大堆化
* 将数组构建为最大堆的线性复杂度为: O(n)
* @param arr 对应数组
*/
private static void buildMaxHeap(int arr[]){
for (int i=(arr.length-1)/2; i>=0; i--){ //必须从大到小
maxHeapify(arr, i, arr.length-1);
}
}这样，我们就对这个数组进行最大堆化了。
接下来就是要对这个最大堆进行排序，思路就是，我们每次都让第一个根节点(arr[0])与最后一个节点交换，再做最大堆化，实现：
/**
* 堆排序算法：
* 不停交换a[0]到最后
* @param arr 待排序数组
*/
private static void heapSort(int[] arr) {
//将数组最大堆化
buildMaxHeap(arr);
for (int i=arr.length-1; i>0; i--){
arr[0] = arr[0]^arr[i];
arr[i] = arr[i]^arr[0];
arr[0] = arr[0]^arr[i];
//将第一个(根)继续进行最大堆化,
//但经过上面的交换操作, 会依次排除排除倒数第i-1元素
maxHeapify(arr, 0, i-1);
}
}int arr[] = new int[]{4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
heapSort(arr);
