堆排序实现:
我们利用最大堆来实现排序,先了解下什么是最大堆呢,看图就明白了:
最大堆:所有根节点都必须大于其孩子。
- 那么对于一个普通的数组,我们要怎么让其变成最大堆呢,比如:
先看看怎么对一颗子树进行最大堆化,其实现代码为:
/**
* 最大堆化数组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);
堆排序时间复杂度为nlgn.