目錄
前言：
堆排序（以排升序為例）
步驟（用大根堆，倒這排，排升序）：
1.先把要排列的數(shù)組建立成大根堆
2.堆頂元素（82）和最后一個元素交換（2）
3.無視掉交換后的元素（82），對（2）進(jìn)行向下調(diào)整
翻譯成代碼
mian方法：
heapSortUp方法：
siftDown方法：
堆排序時間復(fù)雜度分析：
前言：
本文章以升序為例進(jìn)行講解（實際上兩種排列時間復(fù)雜度都一樣，只是比較方式和建立大小堆恰好相反）
文章涉及：
1.向下調(diào)整算法
2.建堆的方式及其時間復(fù)雜度
3.堆排序步驟和時間復(fù)雜度分析
注意：如果1，2點還不了解，建議學(xué)習(xí)完之后在來學(xué)習(xí)堆排序，才能明白下邊講的是什么。
這里有小編自己寫的鏈接，詳細(xì)介紹了堆的創(chuàng)建以及向下/向上調(diào)整算法：優(yōu)先級隊列（堆）
堆排序（以排升序為例）
如果是排升序，要建立大根堆，反之亦然。
排降序，建立小堆
為什么？
看完他的原理，就知道了。
以數(shù)組array={
4,6, 82, 7, 8, 9, 3, 2
}
為例
步驟（用大根堆，倒這排，排升序）：
1.先把要排列的數(shù)組建立成大根堆
2.堆頂元素（82）和最后一個元素交換（2）
3.無視掉交換后的元素（82），對（2）進(jìn)行向下調(diào)整
此時又變成了大根堆（無視已經(jīng)排好的82）：
此時的82已經(jīng)被排號了
其是堆排序的整體思路已經(jīng)講完了，接下來就是循環(huán)執(zhí)行2，3點
3和9換位置，然后無視排好的82，9，對3進(jìn)行向下調(diào)整：
在向下調(diào)整完之后，又是一個大根堆，我們繼續(xù)，循環(huán)這個邏輯，最終的結(jié)果就變成了：
這時，就是一個升序的數(shù)組了。
翻譯成代碼
mian方法：
public class Test {
public static void main(String[] args) {
int[] arr = new int[]{4,6, 82, 7, 8, 9, 3, 2};//要排的數(shù)組
BigHeap bigHeap = new BigHeap();//這個是我自己寫的大根堆
bigHeap.init(arr);//把數(shù)組傳入對象
bigHeap.creatHeap();//先建立起大堆
bigHeap.heapSortUp();//進(jìn)行堆排序
}
}heapSortUp方法：
1.我的堆，底層使用elem的數(shù)組實現(xiàn)的?。。。?！
2.useSize是堆的容量
3.swap的兩個參數(shù)都是數(shù)組的下標(biāo)
public int[] heapSortUp() {
int endIndex = useSize - 1;//最后一個下標(biāo)的位置(也就是容量減1)
while (endIndex > 0) {//如果等于零，就不用交換了
swap(0, endIndex);//頂元素和最后一個元素交換
endIndex--;//最后一個下標(biāo)--，就可以起到無視排號數(shù)，的作用
siftDown(0, endIndex);
}
return elem;
}siftDown方法：
public void siftDown(int parent, int end) {//parent end都是有效下標(biāo)
int child = 2 * parent + 1;//默認(rèn)是左孩子
while (child <= end) {//調(diào)整到最后一個子節(jié)點，為止
//先判斷是否有右孩子
if (child + 1 <= end) {//如果有判斷誰大，大的當(dāng)左孩子
if (elem[child] < elem[child + 1]) {
child++;
}
}
//左孩子在和父節(jié)點進(jìn)行比較
if (elem[child] > elem[parent]) {//如果孩子節(jié)點大，那么父子交換位置
swap(child, parent);
} else {
break;//如果父節(jié)點已經(jīng)是最大的就不用調(diào)整了，這棵樹就是大根堆
//因為我們會從后往前，把這棵樹（數(shù)組）一次遍歷調(diào)整完
}
//下面繼續(xù)往往下面調(diào)整
parent = child;//當(dāng)前的父親，變成自己的孩子
child = parent * 2 + 1;//孩子變成孩子的孩子
}
}堆排序時間復(fù)雜度分析：
其實很簡單，上面我們一共說了三個方法：
1.main
2.heapSortUp
3.siftDown
我們從main方法切入，實際上執(zhí)行堆排序的程序就是這兩步：
public static void main(String[] args) {
int[] arr = new int[]{4,6, 82, 7, 8, 9, 3, 2};
BigHeap bigHeap = new BigHeap();
bigHeap.init(arr);
//這兩步：
bigHeap.creatHeap();//先創(chuàng)建大根堆
bigHeap.heapSortUp();//堆排序，內(nèi)部實現(xiàn)等一下看
}學(xué)了堆我們都直到，建堆的時間復(fù)雜度是O(N)
然后在加上heapSortUp的時間復(fù)雜度，不就是堆排序的時間復(fù)雜度了嗎？
具體看一下，heapSortUp:
public int[] heapSortUp() {
int endIndex = useSize - 1;
while (endIndex > 0) {
swap(0, endIndex);
endIndex--;
siftDown(0, endIndex);
}
return elem;
}useSize和siftDown是我們要計算的時間復(fù)雜度，其他都是常量不用管
useSize實際上就是所給數(shù)組的長度嘛，就是N咯，
學(xué)了siftDown就是向下調(diào)整算法，向下調(diào)整算法和向上調(diào)整算法的時間復(fù)雜度都是logN(以2為底)-----》至于怎么算的，可以看小編文章前言部分的鏈接
所以堆排序的時間復(fù)雜度==O(useSize)+O(siftDown)*O(creatHeap)=N+N*logN文章來源：http://www.zghlxwxcb.cn/news/detail-857270.html
然后取得最高階，則時間復(fù)雜度就是O（N*logN）文章來源地址http://www.zghlxwxcb.cn/news/detail-857270.html
到了這里，關(guān)于為什么堆排序的時間復(fù)雜度是O(N*logN)?的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
