堆排序基本介紹
- 堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，堆排序是一種選擇排序，它的最好、最壞、平均時(shí)間復(fù)雜度均為O(nlogn)，它是不穩(wěn)定排序。
- 堆是具有以下性質(zhì)的完全二叉樹(shù)：每個(gè)節(jié)點(diǎn)的值都大于等于其左右子節(jié)點(diǎn)的值，稱為大頂堆，注意：沒(méi)有要求最有子節(jié)點(diǎn)值得大小關(guān)系。
- 每個(gè)節(jié)點(diǎn)的值都小于等于左右子節(jié)點(diǎn)的值，稱為小頂堆。
- 大頂堆的特點(diǎn)：arr[i ] >= arr[2i+1] && arr[i] >= arr[2i+2], i 對(duì)應(yīng)第幾個(gè)節(jié)點(diǎn)，i 從編號(hào)0開(kāi)始。
- 小頂堆的特點(diǎn): arr[i ] <= arr[2i+1] && arr[i] <= arr[2i+2], i 對(duì)應(yīng)第幾個(gè)節(jié)點(diǎn)，i 從編號(hào)0開(kāi)始。
- 一般升序采用大頂堆，降序采用小頂堆。
堆排序基本思想
- 將待排序序列構(gòu)造成一個(gè)大頂堆
- 此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。
- 將其與數(shù)組末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。
- 然后將剩余 n-1 個(gè)元素重新構(gòu)建成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列。
可以看到在構(gòu)建大頂堆的過(guò)程中，元素的個(gè)數(shù)逐漸減少，最后得到一個(gè)有序序列了
一個(gè)數(shù)組中非葉子節(jié)點(diǎn)的個(gè)數(shù) = arr.length / 2 - 1
代碼案例
package com.xie.tree;
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 800000000);
}
long start = System.currentTimeMillis();
heapSort(arr);
long end = System.currentTimeMillis();
System.out.println("耗時(shí)：" + (end - start) + "ms");
/**
* 800萬(wàn)數(shù)據(jù)
* 堆排序!!
* 耗時(shí)：2482ms
*/
}
public static void heapSort(int[] arr) {
int temp = 0;
System.out.println("堆排序!!");
//1.將無(wú)序序列構(gòu)成一個(gè)堆，根據(jù)升序降序需求選擇大頂堆或小頂堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
//2.將堆頂元素與數(shù)組末尾元素交換，將最大元素"沉"到數(shù)組末端
//3.重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個(gè)序列有序。
for (int j = arr.length - 1; j > 0; j--) {
//交換
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
}
/**
* 將一個(gè)數(shù)組（二叉樹(shù)），調(diào)整成一個(gè)大頂堆
* 功能：完成將以 i 對(duì)應(yīng)的非葉子節(jié)點(diǎn)的樹(shù)調(diào)整成大頂堆
*
* @param arr 待調(diào)整的數(shù)組
* @param i 表示非葉子節(jié)點(diǎn)在數(shù)組的索引
* @param length 表示對(duì)多少個(gè)元素進(jìn)行調(diào)整,length在逐漸減少
*/
public static void adjustHeap(int[] arr, int i, int length) {
//先取出當(dāng)前元素的值，保存在臨時(shí)變量
int temp = arr[i];
//k = 2 * i + 1 是i節(jié)點(diǎn)的左子節(jié)點(diǎn)
for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
//當(dāng)左子節(jié)點(diǎn)值小于右子節(jié)點(diǎn)值
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;//k指向右子節(jié)點(diǎn)
}
//如果子節(jié)點(diǎn)值大于父節(jié)點(diǎn)值
if (arr[k] > temp) {
//把較大的值賦給當(dāng)前節(jié)點(diǎn)
arr[i] = arr[k];
//!!! i指向k 繼續(xù)循環(huán)比較
i = k;
} else {
break;
}
}
//當(dāng)for循環(huán)結(jié)束后，我們已經(jīng)將以 i 為父節(jié)點(diǎn)的樹(shù)的最大值，放在了最頂。
//將temp值放到調(diào)整后的位置
arr[i] = temp;
}
}
原文地址：https://www.toutiao.com/i6935055440891986470/
