这篇博客从以下几个方面来说:
- 什么是最大堆以及代码实现
- 堆排序基础代码
- 一次优化(提高效率)
- 二次优化(原地堆排序,无需额外空间)
1.什么是最大堆以及代码实现
这里可以参考:堆与最大堆
2.堆排序基础代码
import com.heap.MaxHeap;
import utils.CreateRandom;
public class HeapSort {
//堆排序,将需要排序的数组中的元素全部依次入堆,然后反向的取出最大值.
// 算法复杂度 O(n * log n)
public static int[] heapSort_1(int[] arr) {
MaxHeap maxHeap = new MaxHeap(arr.length);
for (int anArr : arr) {
maxHeap.insert(anArr);
}
for (int i = arr.length - 1; i >= 0; i--) {
arr[i] = maxHeap.extrackMax();
}
return arr;
}
}
3.一次优化
import com.heap.MaxHeap;
import utils.CreateRandom;
public class HeapSort {
/*优化1:Heapify
* 最大堆特性:
* 一个没有子节点的节点,可以看做是只有一个根节点的堆,
* arr[count / 2] 即为堆中第一个拥有节点的节点
* 因此只需要从下向上的,依次执行shiftDown操作,由小的堆逐渐变成大的堆就可以了
* 算法复杂度 O(n)
* */
public static int[] heapSort_2(int[] arr) {
MaxHeap maxHeap = new MaxHeap(arr);
//在向 MaxHeap 中传入 arr 数组后,整个数组已经满足最大堆
for (int i = arr.length - 1; i >= 0; i--) {
arr[i] = maxHeap.extrackMax();
}
return arr;
}
}
4.二次优化(原地堆排序)
import com.heap.MaxHeap;
import utils.CreateRandom;
public class HeapSort {
/*优化2:原地堆排序
* 在最大堆中,将第一个位置的值(同时也是最大值)与数组最后一个位置交换位置,在原数组的基础上直接得到有序数组,
* 而不需要开辟新的数组空间来存储堆中排好序的元素.
* */
public static int[] heapSort_3(int[] arr) {
MaxHeap maxHeap = new MaxHeap(arr);
return maxHeap.sortInside();
}
}