溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關java中如何實現一個堆排序，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
1 堆排序
堆是一種重要的數據結構，分為大根堆和小根堆，是完全二叉樹, 底層如果用數組存儲數據的話，假設某個元素為序號為i(Java數組從0開始,i為0到n-1),如果它有左子樹，那么左子樹的位置是2i+1，如果有右子樹，右子樹的位置是2i+2，如果有父節點，父節點的位置是(n-1)/2取整。最大堆的任意子樹根節點不小于任意子結點，最小堆的根節點不大于任意子結點。
所謂堆排序就是利用堆這種數據結構的性質來對數組進行排序，在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的性質可知，最大的值一定在堆頂。堆排序一種不穩定的排序算法，其時間復雜度為O(nlogn)。
2 算法思想
（1）構建最大堆；
（2）選擇頂，并與第0位置元素交換；
（3）由于步驟（2）的的交換可能破環了最大堆的性質，即第0位置的元素不再是最大元素，則需要調用maxHeap調整堆(沉降法)，根據實際情況重復步驟（2）。
堆排序中最重要的算法就是maxHeap，該函數假設一個元素的兩個子節點都滿足最大堆的性質(即左、右子樹都是最大堆)，只有根元素可能違反最大堆性質，那么把該元素以及左右子節點的最大元素找出來，如果該元素已經最大，那么整棵樹都是最大堆，程序退出，否則交換根元素與最大元素的位置，繼續調用maxHeap構建最大元素所在的子樹。
3 Java代碼
public class HeapSort {
public static void main(String[] args) {
int[] arr = {3, 2, 1, 0, -1, -2, -3};
System.out.println("Before heap:");
printArray(arr);
heapSort(arr);
System.out.println("After heap sort:");
printArray(arr);
}
public static void heapSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
buildMaxHeap(arr); //構建最大堆
for (int i = arr.length - 1; i >= 1; i--) {
exchangeElements(arr, 0, i); //交換堆頂和第0位置元素
maxHeap(arr, i, 0); //因為交換元素后，有可能違反堆的性質，所以沉降元素
}
}
private static void buildMaxHeap(int[] arr) { //構建最大堆
if (arr == null || arr.length <= 1) {
return;
}
int half = arr.length / 2;
for (int i = half; i >= 0; i--) {
maxHeap(arr, arr.length, i);
}
}
private static void maxHeap(int[] arr, int heapSize, int index) {
int left = index * 2 + 1; //左子樹上的元素
int right = index * 2 + 2; //右子樹上的元素
int largest = index; //初始化最大元素
if (left < heapSize && arr[left] > arr[index]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (index != largest) { //判斷根元素是否為最大元素
exchangeElements(arr, index, largest);
maxHeap(arr, heapSize, largest);
}
}
public static void printArray(int[] arr) { //打印數組
System.out.print("{");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
public static void exchangeElements(int[] arr, int index1, int index2) { //交換元素
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}以上就是java中如何實現一個堆排序，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
