死磕資料結構與演算法（排序）--堆排序，才疏學淺，如有錯誤，及時指正
- 八大排序演算法
- 1. [冒泡排序演算法](https://blog.csdn.net/qq_41497756/article/details/108816158)
- 2. [選擇排序演算法](https://blog.csdn.net/qq_41497756/article/details/108816431)
- 3. 插入排序冒泡演算法
- 4. 希爾排序冒泡演算法
- 5. [快速插入冒泡演算法](https://blog.csdn.net/qq_41497756/article/details/108815762)
- 6. [歸并排序冒泡演算法](https://blog.csdn.net/qq_41497756/article/details/108836236)
- 7. [基數排序冒泡演算法](https://editor.csdn.net/md/?articleId=108843355)
- 8. 堆排序演算法
- 堆排序
- 1. 概念以及思路
- 1. 什么是堆？
- 2. 什么是堆排序？
- 2. 圖解程序
- 3. 示例代碼
- 總結
八大排序演算法
1. 冒泡排序演算法
2. 選擇排序演算法
3. 插入排序冒泡演算法
4. 希爾排序冒泡演算法
5. 快速插入冒泡演算法
6. 歸并排序冒泡演算法
7. 基數排序冒泡演算法
8. 堆排序演算法
堆排序
1. 概念以及思路
1. 什么是堆？
堆通常是一個可以被看做一棵樹的陣列物件，堆總是滿足以下性值：
堆中某個節點的值總是不大于或不小于其父節點的值，
堆總是一棵完全二叉樹，
根節點最大的堆叫做大頂堆，根節點最小的堆叫做小頂堆，
大頂堆示意圖：
小頂堆示意圖：
2. 什么是堆排序？
堆排序是利用堆這種資料結構而設計的一種排序演算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為O(nlogn)，它是不穩定排序，
2. 圖解程序
基本思想：
- 將要排序的陣列構造成一個大頂堆
- 將堆頂的元素與末尾元素進行交換，此時末尾元素就是最大值
- 將剩余n-1個元素重新構成一個，這樣得到n個元素的次小值，反復執行1、2操作，直到要執行的元素長度為1.
詳細操作看代碼中的注釋，
3. 示例代碼
package Tree;
import java.util.Arrays;
public class heapSort {
public static void main(String[] args) {
int[] arr = {4,8,5,9,13,6,3,1};
heapSort( arr );
System.out.println( Arrays.toString(arr));
}
/**
* 堆排序
* 1. 將要排序的陣列構造成一個大頂堆
* 2. 將堆頂的元素與末尾元素進行交換，此時末尾元素就是最大值
* 3. 將剩余n-1個元素重新構成一個，這樣得到n個元素的次小值，反復執行1、2操作，直到要執行的元素長度為1.
* @param arr 要進行排序的陣列
*/
public static void heapSort(int[] arr){
//1. 第一次構建一個大頂堆
for (int i = arr.length/2-1; i >= 0; i--) {
//從第一個非葉子節點從下至上，從右到左調整結構
adjustHeap( arr, i, arr.length );
}
for (int j = arr.length - 1; j > 0 ; j--) {
//將堆頂元素與末尾元素進行交換
int temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
//對堆進行調整，此時從堆頂開始做一次調整就可以得到一個大頂堆
//因為經過第一次調整之后，父節點的子節點都已經比它的子節點要大了，只有交換之后的根節點不滿足要求，所以此時只需要i=0做一次調整即可，
adjustHeap( arr, 0, j );
}
}
/**
* 該方法用來
* @param arr 要調整的陣列(樹)
* @param i 開始調整的葉子節點的下標
* @param length 調整的長度
*/
public static void adjustHeap (int[] arr, int i, int length){
int temp = arr[i]; //取出當前元素i
//對節點下面的元素進行遍歷
//從i的左子節點進行回圈，也就是i*2+1處開始
for (int k = i * 2 + 1; k < length; k++) {
if(k + 1 < length && arr[k] < arr[k + 1]){
k++; //對下一個節點做判斷
}
//如果子節點大于父節點，把子節點的值給父節點
if(arr[k] > temp){
arr[i] = arr[k]; //把較大的值，賦值給當前節點
i = k; //把i指向k，繼續回圈比較
}else {
break;
}
}
arr[i] = temp; //temp放入最終的位置
}
}
總結
本文使用java完成了一個簡單的堆排序演算法，以及介紹了堆排序的相關概念，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/192197.html
標籤：其他
上一篇：Java入門----猜拳小游戲