堆排序問(wèn)題
最近回顧算法，看了一下堆排序的原理，有點(diǎn)小疑問(wèn)，求大神解答。
具體問(wèn)題如下：
以升序?yàn)槔?，我們需要?gòu)建一個(gè)大頂堆，在構(gòu)建過(guò)程中，我們需要對(duì)每一個(gè)非葉子節(jié)點(diǎn)進(jìn)行及其左右子節(jié)點(diǎn)進(jìn)行比較，找到其最大值，并進(jìn)行相應(yīng)的交換。而在每次交換完成后，又需要對(duì)交換了的子節(jié)點(diǎn)再進(jìn)行一次交換。
有一個(gè)無(wú)序數(shù)組[4,6,8,5,9]，構(gòu)建的順序二叉樹(shù)如圖。
我們需要將6和9交換，得到結(jié)果如圖：
image.png
然后將4和9交換得到結(jié)果如圖：
image.png
問(wèn)題來(lái)了，此時(shí)我們其實(shí)已經(jīng)得到了堆頂元素最大值9，其實(shí)可以直接將它與6進(jìn)行交換，然后再對(duì)剩余部分進(jìn)行上述操作，那么我們?yōu)槭裁催€要去將4和6進(jìn)行交換，得到一個(gè)標(biāo)準(zhǔn)的大頂堆，然后再將4和9交換呢？
更新：搞清楚了來(lái)龍去脈，一下是用java的堆排序代碼
package Sort;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {4, 6, 8, 5, 9};
heapSort(arr);
}
public static void heapSort(int[] arr) {
int temp = 0;
//1.第一次遍歷完成之后就得到一個(gè)大頂堆
for (int i = arr.length - 1; i >= 0; i--) {//從倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始遍歷
adjustHeap(arr, i, arr.length);
}
//2.得到大頂堆后，將堆頂元素與末尾元素交換
for (int i = arr.length - 1; i > 0; i--) {
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//3.繼續(xù)從堆頂元素開(kāi)始向下交換
adjustHeap(arr, 0, i);
}
System.out.println(Arrays.toString(arr));
}
/**
* @param arr 原數(shù)組
* @param i 需要調(diào)整的非葉子節(jié)點(diǎn)數(shù)組索引
* @param len 未完成排序的數(shù)組數(shù)組長(zhǎng)度，len在逐漸減少
*/
public static void adjustHeap(int[] arr, int i, int len) {
int temp = arr[i];
for (int k = 2 * i + 1; k < len; k = k * 2 + 1) {//k為左子節(jié)點(diǎn)
if (k + 1 < len && arr[k] < arr[k + 1]) {//左子節(jié)點(diǎn)小于右子節(jié)點(diǎn)
k++;//將指針移到右子節(jié)點(diǎn)
}
if (arr[k] > temp) {//如果子節(jié)點(diǎn)值大于父節(jié)點(diǎn)，則應(yīng)該交換
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;//將temp值放到調(diào)整后的位置
}
}
