请用Java写一个大根堆排序
时间: 2023-05-28 17:01:05 浏览: 117
public class HeapSort {
private static int[] arr;
public static void heapSort(int[] array) {
if (array == null || array.length == 0) {
return;
}
arr = array;
int len = arr.length;
//建立初始大根堆
for (int i = len / 2; i >= 0; i--) {
heapAdjust(i, len - 1);
}
//将堆顶元素(最大值)与堆中最后一个元素交换,并缩小堆的范围,再次调整堆结构,直到完全有序
for (int i = len - 1; i >= 0; i--) {
swap(0, i);
heapAdjust(0, i - 1);
}
}
private static void heapAdjust(int start, int end) {
int tmp = arr[start];
int child = start * 2 + 1;
while (child <= end) {
//左右子节点比较,取较大者
if (child + 1 <= end && arr[child] < arr[child + 1]) {
child++;
}
if (tmp >= arr[child]) {
break;
}
arr[start] = arr[child];
start = child;
child = start * 2 + 1;
}
arr[start] = tmp;
}
private static void swap(int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] array = {10,9,8,7,6,5,4,3,2,1};
heapSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
阅读全文