算法描述
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
动图演示
代码实现
public class Heap {
private final static int[] arr = new int[]{1, 11, 11, 2, 12, 3, 4, 56, 33, 5, 6};
private static int len = arr.length;
public static int[] sort(int[] arr) {
build(arr);
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
public static void build(int[] arr) {
int len = arr.length;
for (int i = Math.floorDiv(len, 2); i >= 0; i--) {
heapify(arr, i);
}
}
public static void heapify(int[] arr, int midPoint) {
int leftPoint = 2 * midPoint + 1;
int rightPoint = 2 * midPoint + 2;
int largestPoint = midPoint;
if (leftPoint < len && arr[leftPoint] > arr[largestPoint]) {
largestPoint = leftPoint;
}
if (rightPoint < len && arr[rightPoint] > arr[largestPoint]) {
largestPoint = rightPoint;
}
if (largestPoint != midPoint) {
swap(arr, midPoint, largestPoint);
heapify(arr, largestPoint);
}
}
public static void swap(int[] arr, int midPoint, int largestPoint) {
int temp = arr[midPoint];
arr[midPoint] = arr[largestPoint];
arr[largestPoint] = temp;
}
public static void main(String[] args) {
sort(arr);
Arrays.stream(arr).forEach(System.out::println);
}
}