堆排序是一種效率較高的排序算法,其基本思想是將待排序序列構建成一個大頂堆,然后將堆頂元素與末尾元素交換,然后重新調整堆,重復此過程直到整個序列有序。
下面是Java實現堆排序的代碼:
public class HeapSort {
public static void heapSort(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 = { 4, 10, 3, 5, 1 };
heapSort(arr);
System.out.println(Arrays.toString(arr)); // 輸出:[1, 3, 4, 5, 10]
}
}
在主函數中,我們創建了一個待排序的數組arr,然后調用heapSort方法進行堆排序。最后打印排序后的數組。運行結果為[1, 3, 4, 5, 10]。