堆排序（Heap Sort）
- 1、堆介紹
- 2、演算法介紹
- 3、圖解
- 4、代碼實作
- 5、執行結果
- 6、其他演算法
1、堆介紹
大頂堆： 非葉子結點的資料要大于或等于其左，右子節點的資料
小頂堆： 非葉子結點的資料要小于或等于其左，右子節點的資料
2、演算法介紹
- 先從后面的非葉子結點從后向前將結點構建成一個大頂堆（小頂堆），
- 此時根節點就是最大的資料（最小的資料），然后將根節點與陣列最后一位進行交換，
- 交換后再從根節點開始構建堆（此時樹的長度應該減一，因為最大的數已經確定了），
- 重復執行2-3步驟，直到資料有序，
3、圖解
4、代碼實作
package sort;
import java.util.Arrays;
/**
* <p>
*
* </p>
*
* @author: D
* @since: 2020/9/11
* @version: 1
*/
public class HeapSortDemo {
public static void main(String[] args) {
int[] arr = {117, 101, 106, 100, 112, 60, 90, 110};
heapSort(arr);
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void heapSort(int[] arr) {
int temp;
System.out.println("從后向前構建堆");
//從后面的非葉子結點進行調整陣列為大頂堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
System.out.println("非葉子結點：" + i);
bigTopPile(arr, i, arr.length);
}
System.out.println("從根節點開始構建堆");
for (int j = arr.length - 1; j > 0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
System.out.println("確認下標為" + j + "：" + Arrays.toString(arr));
// 從根節點開始調整資料為大頂堆
bigTopPile(arr, 0, j);
}
}
/**
* 將陣列變為一個大頂堆
*
* @param arr 陣列
* @param nonLeafNode 非葉子結點在陣列中的下標
* @param length 調整的陣列長度
*/
private static void bigTopPile(int[] arr, int nonLeafNode, int length) {
System.out.println("構建前陣列：" + Arrays.toString(arr));
//保存非葉子結點
int temp = arr[nonLeafNode];
System.out.println("非葉子結點資料：" + temp);
// index = nonLeafNode * 2 + 1 index為非葉子結點的左子結點
for (int index = nonLeafNode * 2 + 1; index < length; index = index * 2 + 1) {
System.out.println("左子節點：" + index);
//左子節點小于右子節點 右子節點就是左子節點加1
if (index + 1 < length && arr[index] < arr[index + 1]) {
System.out.println("左子節點小于右子節點，指標指向右子節點");
//左子節點小于右子節點 那么將index此時指向右子節點
index++;
}
//如果子節點大于父節點 則進行交換
if (arr[index] > temp) {
System.out.println("子節點大于父節點，進行交換");
arr[nonLeafNode] = arr[index];
nonLeafNode = index;
} else {
break;
}
}
arr[nonLeafNode] = temp;
System.out.println("構建后陣列：" + Arrays.toString(arr));
System.out.println();
}
}
5、執行結果
6、其他演算法
選擇排序（Selection Sort）
插入排序（Insertion Sort）
希爾排序（Shell Sort）
冒泡排序（Bubble Sort）
快速排序（Quick Sort）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/33116.html
標籤：其他
上一篇：C++語言