堆排序的概述
堆是具有下列特性的完全二叉樹：每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子的節(jié)點(diǎn)的值溃卡，成為大頂堆竞漾，或者每個(gè)節(jié)點(diǎn)的值都小于或等于其左右孩子節(jié)點(diǎn)的值侮繁，成為小頂堆结窘。
在選擇到最小記錄同時(shí)怖喻，并根據(jù)比較結(jié)果對(duì)其他記錄做出相應(yīng)調(diào)整底哗。這樣的排序整體效率非常高。
堆排序的思路
堆排序（Heap Sort）就是利用堆進(jìn)行排序的方法锚沸。他的基本思想是跋选，將待排序的序列構(gòu)造成一個(gè)大頂堆，此時(shí)哗蜈，整個(gè)序列的最大值就是對(duì)定的根節(jié)點(diǎn)前标。將他移走（其實(shí)就是將其余對(duì)數(shù)組的末尾元素交換，此時(shí)末尾元素就是最大值）距潘，然后將剩余的n-1個(gè)序列重新構(gòu)成一個(gè)堆炼列，這樣就會(huì)得到n個(gè)元素中的次小值。如此反復(fù)音比，便能得到一個(gè)有序序列俭尖。
堆排序的復(fù)雜度
他的運(yùn)行時(shí)間主要是消耗在初始結(jié)構(gòu)建堆和在重建堆時(shí)的反復(fù)篩選上。
在構(gòu)建堆的過程中洞翩，因?yàn)槲覀兪峭耆鏄鋸淖钕聦幼钣疫叺姆墙K端節(jié)點(diǎn)開始構(gòu)建稽犁，將它與其他孩子進(jìn)行比較和有必要的交換，對(duì)于每個(gè)非終端節(jié)點(diǎn)來說骚亿，其實(shí)最多進(jìn)行兩次比較和互換已亥，因此整個(gè)構(gòu)建堆的時(shí)間復(fù)雜度為O(n)。
在正式排序時(shí)来屠，第i次取堆頂記錄重建堆需要用O(logi)的時(shí)間虑椎，并且需要取n-1次堆頂記錄。因此俱笛，重建堆的時(shí)間復(fù)雜度為O(nlogn)捆姜。
空間復(fù)雜度上，它只有一個(gè)用來交換的暫存單元嫂粟，也非常不錯(cuò)娇未，不過由于記錄的比較與交換是跳躍式進(jìn)行，因此堆排序也是一種不穩(wěn)定的排序方法星虹。
堆排序的JAVA實(shí)現(xiàn)
public class Main {
public static void main(String[] args) {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = Math.toIntExact(Math.round(Math.random() * 1000));
}
HeapSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void HeapSort(int[] arr) {
int i;
for (i = arr.length / 2 - 1; i >= 0; i--) {
HeapAdjust(arr, i, arr.length);
}
for (i = arr.length - 1; i >= 1; i--) {
swap(arr, 0, i);
HeapAdjust(arr, 0, i);
}
}
private static void HeapAdjust(int[] arr, int s, int m) {
int temp;
temp = arr[s];
int index = 2 * s + 1;
while (index < m) {
if (index + 1 < m) {
if (arr[index] < arr[index + 1]) {
index++;
}
}
if (arr[index] > temp) {
arr[s] = arr[index];
s = index;
index = 2 * s + 1;
} else {
break;
}
}
arr[s] = temp;
}
private static void swap(int[] arr, int s, int e) {
int temp = arr[s];
arr[s] = arr[e];
arr[e] = temp;
}
}