目錄

1. 算法介紹

2. 執(zhí)行流程??????

3.?代碼實(shí)現(xiàn)

4. 性能分析

---

1. 算法介紹

堆是一種數(shù)據(jù)結(jié)構(gòu)，可以把堆看成一棵完全二叉樹，這棵完全二叉樹滿足：任何一個(gè)非葉結(jié)點(diǎn)的值都不大于(或不小于)其左右孩子結(jié)點(diǎn)的值。若父親大孩子小，則這樣的堆叫作大頂堆;若父親小孩子大，則這樣的堆叫作小頂堆。

根據(jù)堆的定義知道，代表堆的這棵完全二叉樹的根結(jié)點(diǎn)的值是最大(或最小)的，因此將一個(gè)無序序列調(diào)整為一個(gè)堆，就可以找出這個(gè)序列的最大(或最小)值，然后將找出的這個(gè)值交換到序列的最后(或最前)，這樣，有序序列關(guān)鍵字增加1個(gè)，無序序列中關(guān)鍵字減少1個(gè)，對(duì)新的無序序列重復(fù)這樣的操作，就實(shí)現(xiàn)了排序。這就是堆排序的思想。

堆排序中最關(guān)鍵的操作是將序列調(diào)整為堆。整個(gè)排序的過程就是通過不斷調(diào)整，使得不符合堆定義的完全二叉樹變?yōu)榉隙讯x的完全二叉樹。

2. 執(zhí)行流程??????

建堆是先從自下而上，從右往左建

初始堆的每一個(gè)結(jié)點(diǎn)都要滿足堆的定義，也就是父節(jié)點(diǎn)的值大于左右孩子結(jié)點(diǎn)的值！！！

選出最大值，是將根結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)互換，然后繼續(xù)構(gòu)建大頂堆！！！

???堆頂和最后一個(gè)元素交換，才算一趟，也是該趟的最終序列結(jié)果！！！

建堆和排序結(jié)果是兩個(gè)階段，但同屬于一趟中。

圖示如下：

3.?代碼實(shí)現(xiàn)

為了三個(gè)步驟：

步驟一：先建堆（大根堆或者小根堆）

步驟二：交完堆頂和最后一個(gè)元素，然后堆的大小減一

步驟三：向下調(diào)整堆

步驟一只需實(shí)現(xiàn)一次，步驟二和步驟三循環(huán)執(zhí)行，得到最終的有序序列。

    //開始排序：堆排序分為三個(gè)功能 ①開始建堆，②交換，③向下調(diào)整，重復(fù)②和③步public static void heapSort(int[] array,int len){int end = len - 1;//確定最后一個(gè)結(jié)點(diǎn)的下標(biāo)createHeap(array);//建堆//當(dāng)只剩下一個(gè)結(jié)點(diǎn)的時(shí)候，就不需要交換while(end > 0){//交換swap(array,0,end);//向下調(diào)整shiftDown(array,0,end);//調(diào)整完一個(gè)結(jié)點(diǎn)，下一個(gè)end--;}}//交換數(shù)據(jù)public static void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}//堆排序（大根堆）//從上往下建堆，所以先找父節(jié)點(diǎn)，再找孩子結(jié)點(diǎn)public static void createHeap(int[] array){for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--){shiftDown(array,parent,array.length);}}//向下調(diào)整public static void shiftDown(int[] array,int parent,int len){//定義一個(gè)記錄孩子下標(biāo)的變量（左孩子）int child = 2 * parent + 1;//判斷父節(jié)點(diǎn)和孩子結(jié)點(diǎn)的大小，至少左孩子要存在while(child < len){//比較左右孩子if((child + 1) < len && array[child] < array[child + 1]){child++;}//判斷父節(jié)點(diǎn)和孩子節(jié)點(diǎn)if(array[child] > array[parent]){swap(array,child,parent);parent = child;child = 2 * parent + 1;}else{break;}}}

    public static void main(String[] args) {int[] a = {5,4,3,2,1};Sort.heapSort(a, a.length);for (int x : a) {System.out.print(x + " ");}}

4. 性能分析

時(shí)間輔助度	空間復(fù)雜度
O(N*logN)	O(1)
數(shù)據(jù)不敏感	數(shù)據(jù)不敏感

穩(wěn)定性：不穩(wěn)定。

來上解析，怎么計(jì)算這個(gè)時(shí)間復(fù)雜度。

（1）步驟一的時(shí)間復(fù)雜度：首先知道有N個(gè)結(jié)點(diǎn)開始建堆，這個(gè)時(shí)間復(fù)雜度就是O(N)，大家可以去看看這篇文章，里面有講建堆的時(shí)間復(fù)雜度。鏈接如下：

數(shù)據(jù)結(jié)構(gòu)——堆、堆排序和優(yōu)先級(jí)隊(duì)列（代碼為Java版本）

（2）步驟二和步驟三循環(huán)的時(shí)間復(fù)雜度：那么我第一個(gè)結(jié)點(diǎn)交換時(shí)，需要向下調(diào)整為log(N - 1)層；交換第二個(gè)結(jié)點(diǎn)后，需要向下log(N - 2)，接下來就是log(N - 3)，log(N - 4)，……，log1。所以總的調(diào)整次數(shù)是log(N - 1) + log(N - 2) + log(N - 3) + log(N - 4) + …… + log1 = log((N - 1)!)。

我們可以在網(wǎng)上看到堆排序的時(shí)間復(fù)雜度是O(N*logN)，這是堆排序的大致估算（我們算時(shí)間復(fù)雜度都是算個(gè)大概），其實(shí)log((N - 1)!) 約等于 NlogN。下面是我的證明結(jié)果：

① 使用夾逼準(zhǔn)則證明：

先求上限：

再求下限:

因?yàn)?

所以?

當(dāng)??時(shí)，? ? ? ? ? ? ? ?

② 則有：

?? ? ?

③結(jié)論：?既是??的低階函數(shù)，又是??的高階函數(shù)，因此是??的同階函數(shù)！

（3）由于上面的證明步驟，我們可以知道堆排序的時(shí)間復(fù)雜度是???。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?