對(duì)于堆排序會(huì)涉及一些完全二叉樹知識(shí)。對(duì)于待排序列{10, 2, 11, 8, 7}，把它看成是一顆完全二叉樹，如下圖所示。
堆分為大根堆和小根堆：大根堆表示每個(gè)根節(jié)點(diǎn)均大于其子節(jié)點(diǎn)（l(i) >= l(2i) && l(i) >= l(2i + 1)），小根堆表示每個(gè)根節(jié)點(diǎn)均小于其子節(jié)點(diǎn)（l(i) <= l(2i) && l(i) <= l(2i + 1)）。（在完全二叉樹中第i個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)為2i，其右字節(jié)點(diǎn)為2i + 1）
本文將以大根堆的構(gòu)建作為示例進(jìn)行講解。
堆排序的第一步——構(gòu)建初始堆。如何構(gòu)建初始堆呢？根據(jù)定義，關(guān)鍵點(diǎn)在于每個(gè)根節(jié)點(diǎn)。觀察上述待排序列的完全二叉樹，不難發(fā)現(xiàn)存在節(jié)點(diǎn)2和節(jié)點(diǎn)10有子節(jié)點(diǎn)，它們是需要關(guān)注的節(jié)點(diǎn)。
如何定位節(jié)點(diǎn)2呢？發(fā)現(xiàn)它是葉子節(jié)點(diǎn)，或者最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，根據(jù)完全二叉樹的性質(zhì)可知，除根節(jié)點(diǎn)外任意節(jié)點(diǎn)的父節(jié)點(diǎn)的編號(hào)為⌊n / 2⌋。已知n = 5，易知節(jié)點(diǎn)2的編號(hào)為⌊5 / 2⌋ = ②。比較它與左右子節(jié)點(diǎn)的大小并調(diào)整。
最后剩下根節(jié)點(diǎn)10，已知節(jié)點(diǎn)2的編號(hào)為②，② - 1 = ①即得到根節(jié)點(diǎn)10的編號(hào)。比較它與左右子節(jié)點(diǎn)的大小并調(diào)整。
調(diào)整完畢后發(fā)現(xiàn)已經(jīng)構(gòu)成了一個(gè)“大根堆”，示例中的待排序列較為簡(jiǎn)單，再給出一個(gè)較為復(fù)雜的待排序列，觀察其構(gòu)建大根堆的過(guò)程。對(duì)于待排序列{53, 17, 78, 09, 45, 65, 87, 32}，將它看成一顆完全二叉樹。
同樣我們來(lái)看它所需要關(guān)注的節(jié)點(diǎn)有哪些。
根據(jù)第一個(gè)例子，我們很容易能定位節(jié)點(diǎn)09的編號(hào)為⌊8 / 2⌋ = ④，節(jié)點(diǎn)78的編號(hào)為④ - 1 = ③……，依次類推，發(fā)現(xiàn)了一定的規(guī)律，即需要調(diào)整的節(jié)點(diǎn)位置從⌊n / 2⌋開始依次遞減直到根節(jié)點(diǎn)①結(jié)束(⌊n / 2⌋ ~ 1)?，F(xiàn)在開始調(diào)整。
在第四次調(diào)整結(jié)束后發(fā)現(xiàn)節(jié)點(diǎn)53不滿足大根堆的定義，其右子節(jié)點(diǎn)大于它，此時(shí)需要做進(jìn)一步的向下調(diào)整。
注意向下調(diào)整是每次向上調(diào)整的時(shí)候都需要做的判斷是否需要向下調(diào)整，而不是在所有的向上調(diào)整結(jié)束過(guò)后再回過(guò)頭來(lái)向下調(diào)整。這樣大根堆就建立好了，此時(shí)待排序列數(shù)組情況已經(jīng)發(fā)生了改變：{87, 45, 78, 32, 17, 65, 53, 09}。接下來(lái)是如何進(jìn)行排序的問(wèn)題。將大根堆的根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)互換，并調(diào)整二叉樹使其仍然滿足大根堆。
可以看到將根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)呼喚后，待排序列的最大值已經(jīng)放到了數(shù)組的最后一個(gè)位置{……, 87}，此時(shí)完成了第一趟排序，但這第一趟排序還沒(méi)有結(jié)束，此時(shí)除節(jié)點(diǎn)87外，其余節(jié)點(diǎn)并不滿足大根堆的條件，所以需要對(duì)其余節(jié)點(diǎn)進(jìn)行調(diào)整為大根堆。排序過(guò)程不再給出，java和python3的代碼實(shí)現(xiàn)如下。
java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
package com.algorithm.sort.heap;import java.util.arrays;/** * 堆排序 * created by yulinfeng on 6/20/17. */public class heap { public static void main(string[] args) { int[] nums = {53, 17, 78, 09, 45, 65, 87, 32}; nums = heapsort(nums); system.out.println(arrays.tostring(nums)); } /** * 堆排序 * @param nums 待排序數(shù)組序列 * @return 排好序的數(shù)組序列 */ private static int[] heapsort(int[] nums) { for (int i = nums.length / 2 - 1; i >= 0; i--) { heapadjust(nums, i, nums.length); } for (int i = nums.length - 1; i > 0; i--) { int temp = nums[i]; nums[i] = nums[0]; nums[0] = temp; heapadjust(nums, 0, i); } return nums; } /** * 調(diào)整堆 * * @param nums 待排序序列 * @param parent 待調(diào)整根節(jié)點(diǎn) * @param length 數(shù)組序列長(zhǎng)度 */ private static void heapadjust(int[] nums, int parent, int length) { int temp = nums[parent]; int childindex = 2 * parent + 1; //完全二叉樹節(jié)點(diǎn)i從編號(hào)1開始的左子節(jié)點(diǎn)位置在2i，此處數(shù)組下標(biāo)從0開始，即左子節(jié)點(diǎn)所在數(shù)組索引位置為：2i + 1 while (childindex < length) { if (childindex + 1 < length && nums[childindex] < nums[childindex + 1]) { childindex++; //節(jié)點(diǎn)有右子節(jié)點(diǎn)，且右子節(jié)點(diǎn)大于左子節(jié)點(diǎn)，則選取右子節(jié)點(diǎn) } if (temp > nums[childindex]) { break; //如果選中節(jié)點(diǎn)大于其子節(jié)點(diǎn)，直接返回 } nums[parent] = nums[childindex]; parent = childindex; childindex = 2 * parent + 1; //繼續(xù)向下調(diào)整 } nums[parent] = temp; }} |
python3
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#堆排序def heap_sort(nums): for i in range(int(len(nums) / 2 - 1), -1, -1): heap_adjust(nums, i, len(nums)) for i in range(len(nums) - 1, -1, -1): temp = nums[i] nums[i] = nums[0] nums[0] = temp heap_adjust(nums, 0, i) return nums#調(diào)整堆def heap_adjust(nums, parent, length): temp = nums[parent] childindex = 2 * parent + 1 while childindex < length: if childindex + 1 < length and nums[childindex] < nums[childindex + 1]: childindex += 1 if temp > nums[childindex]: break nums[parent] = nums[childindex] parent = childindex childindex = 2 * parent + 1 nums[parent] = temp nums = [53, 17, 78, 09, 45, 65, 87, 32]nums = heap_sort(nums)print(nums) |
以上這篇老生常談比較排序之堆排序就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持服務(wù)器之家。
