java实现堆排序(附完整源码)
时间: 2023-11-11 10:04:18 浏览: 41
好的,下面是Java实现堆排序的完整源码:
```java
public class HeapSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = { 12, 11, 13, 5, 6, 7 };
sort(arr);
System.out.println(Arrays.toString(arr));
}
}
```
这个程序实现了堆排序算法。在 `sort` 函数中,我们首先将待排序数组构建成一个最大堆,然后将堆顶元素与堆底元素交换,再对剩余元素重新进行堆化,直到整个数组有序。
在 `main` 函数中,我们对数组 `{ 12, 11, 13, 5, 6, 7 }` 进行排序,并输出结果。
输出结果如下:
```
[5, 6, 7, 11, 12, 13]
```
可以看到,堆排序算法成功将数组排序。