堆排序Java代码实现
时间: 2024-10-09 13:13:33 浏览: 18
堆排序是一种基于比较的排序算法,它的工作原理是通过建立一个最大堆(或最小堆),然后反复将堆顶元素与末尾交换并将剩余部分再调整成堆来进行排序。以下是Java中堆排序的一个简单实现:
```java
import java.util.Arrays;
public class HeapSort {
public void sort(int[] array) {
int n = array.length;
// Build heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(array, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = array[0];
array[0] = array[i]; // Swap
array[i] = temp;
// call max heapify on the reduced heap
heapify(array, i, 0);
}
}
private void heapify(int[] array, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1;
int right = 2 * i + 2;
// If left child is larger than root
if (left < n && array[left] > array[largest])
largest = left;
// If right child is larger than largest so far
if (right < n && array[right] > array[largest])
largest = right;
// If largest is not root
if (largest != i) {
int swap = array[i];
array[i] = array[largest];
array[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(array, n, largest);
}
}
// Test the code
public static void main(String[] args) {
int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
HeapSort hs = new HeapSort();
hs.sort(arr);
System.out.println("Sorted array is: " + Arrays.toString(arr));
}
}
```
这个程序首先创建最大堆,然后不断将堆顶元素与最后一个元素交换并缩小堆的范围,直到整个数组有序。`heapify()`函数负责维护堆的性质。