6.堆排序
6.1算法思想
堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)（同層節(jié)點(diǎn)不進(jìn)行比較）。并且一般來說，升序排列通過構(gòu)造大頂堆來實(shí)現(xiàn)，降序排列通過構(gòu)造小頂堆來實(shí)現(xiàn)。
這種算法不用額外的空間，空間復(fù)雜度為o（1），時(shí)間復(fù)雜度為o（nlogn）
6.1.1堆
堆是一種完全二叉樹（完全二叉樹 是 一種除了最后一層之外的其他每一層都被完全填充，并且所有結(jié)點(diǎn)都保持向左對齊的樹）
堆有兩種類型: 大頂堆和小頂堆：
大頂堆：每個(gè)結(jié)點(diǎn)的值都大于或等于左右孩子結(jié)點(diǎn)
小頂堆：每個(gè)結(jié)點(diǎn)的值都小于或等于左右孩子結(jié)點(diǎn)
大頂堆和小頂堆可以通過下面的圖進(jìn)行直觀的感受：
6.2 算法過程
- 首先將待排序的數(shù)組構(gòu)造出一個(gè)大頂堆（這里以升序排列為例）
- 取出這個(gè)大頂堆的堆頂節(jié)點(diǎn)(最大值)，與堆的最下最右的元素進(jìn)行交換，然后把剩下的元素再構(gòu)造出一個(gè)大根堆。
- 重復(fù)第二步，直到這個(gè)大根堆的長度為1，此時(shí)完成排序
ps：將數(shù)組中的元素構(gòu)造成大頂堆的時(shí)候，堆頂元素就是所有元素的最大值，而堆的最下最右是數(shù)組的最后一個(gè)元素，這就相當(dāng)于把最大值放在了數(shù)組的最后，然后在對剩下的元素進(jìn)行相同操作。
對于這個(gè)算法的具體過程的圖示，大家可以看一下堆排序圖解這篇博客。
過程動圖如下
6.3 python代碼
6.3.1 遞歸（不對原數(shù)組引入一個(gè)輔助元素）
global
length
# 定義全局變量
def
buildMaxHeap
(
numList
)
:
# 構(gòu)建最大堆，
global
length
length
=
len
(
numList
)
for
i
in
range
(
length
//
2
,
-
1
,
-
1
)
:
# 從最后一個(gè)有子節(jié)點(diǎn)的根節(jié)點(diǎn)節(jié)點(diǎn)開始構(gòu)建的時(shí)候從下往上，從右向左構(gòu)建
heapify
(
numList
,
i
)
def
heapify
(
numList
,
i
)
:
# 堆調(diào)整，將剩下的元素調(diào)整成最大堆
global
left
,
right
,
largest
,
length
leftChildren
=
2
*
i
+
1
rightChildren
=
2
*
i
+
2
largest
=
i
if
leftChildren
<
length
and
numList
[
leftChildren
]
>
numList
[
largest
]
:
# leftChildren < length先判斷是否有子節(jié)點(diǎn)，因?yàn)閜ython數(shù)組下標(biāo)從零開始的緣故，下標(biāo)為length/2的元素可能會沒有子節(jié)點(diǎn)。
largest
=
leftChildren
if
rightChildren
<
length
and
numList
[
rightChildren
]
>
numList
[
largest
]
:
largest
=
rightChildren
if
largest
!=
i
:
# 如果largest（最大的節(jié)點(diǎn)所在的下標(biāo)），不是根節(jié)點(diǎn)，說明這三個(gè)借點(diǎn)不滿足堆的規(guī)則，
# 需要進(jìn)行調(diào)整，根節(jié)點(diǎn)的下標(biāo)是i，最大節(jié)點(diǎn)的下標(biāo)是largest，交換即可。
swap
(
numList
,
i
,
largest
)
# 當(dāng)當(dāng)前的根節(jié)點(diǎn)和子節(jié)點(diǎn)滿足堆的關(guān)系之后，由子節(jié)點(diǎn)作為根節(jié)點(diǎn)的樹可能又不滿足了，必須在對下一層的樹進(jìn)行檢查和調(diào)整。
heapify
(
numList
,
largest
)
def
swap
(
numList
,
i
,
j
)
:
numList
[
i
]
,
numList
[
j
]
=
numList
[
j
]
,
numList
[
i
]
def
heapSort
(
numList
)
:
global
length
buildMaxHeap
(
numList
)
for
i
in
range
(
len
(
numList
)
-
1
,
0
,
-
1
)
:
swap
(
numList
,
0
,
i
)
length
-=
1
# 在調(diào)整的時(shí)候就不會在調(diào)整最后一個(gè)元素了
heapify
(
numList
,
0
)
# 由于交換之前，已經(jīng)都調(diào)整為最大堆了，而交換之后，大部分都符合堆的規(guī)則，
# 只從堆頂元素（下標(biāo)為1）開始，只進(jìn)行局部的調(diào)整就好，
# 這時(shí)候不用再像剛開始構(gòu)建最大堆一樣從下往上，從右往左調(diào)整交換了。
return
numList
numlist
=
[
4
,
5
,
4
,
1
,
8
,
7
,
2
,
6
,
3
]
print
(
heapSort
(
numlist
)
)
6.3.2非遞歸（引入一個(gè)輔助因素，將數(shù)組的下標(biāo)往后加1）
def
swap
(
arr
,
i
,
j
)
:
arr
[
i
]
,
arr
[
j
]
=
arr
[
j
]
,
arr
[
i
]
def
heapAdjust
(
arr
,
start
,
end
)
:
i
=
start
temp
=
arr
[
start
]
j
=
2
*
i
while
j
<=
end
:
if
j
<
end
and
arr
[
j
]
<
arr
[
j
+
1
]
:
j
+=
1
if
arr
[
i
]
<
arr
[
j
]
:
arr
[
i
]
=
arr
[
j
]
i
=
j
j
=
2
*
i
else
:
break
arr
[
i
]
=
temp
def
heapSort
(
numList
)
:
numList
.
insert
(
0
,
0
)
# 由于python，數(shù)組的下標(biāo)從0開始，因此需要加入一個(gè)輔助元素，是所有的元素的下標(biāo)都往后移動一位。
length
=
len
(
numList
)
-
1
firstAdjustRoot
=
length
//
2
for
i
in
range
(
firstAdjustRoot
)
:
# 在構(gòu)造最大堆的時(shí)候，不會對最左側(cè)的0進(jìn)行處理，因?yàn)閕不會取到firstAdjustRoot。
heapAdjust
(
numList
,
firstAdjustRoot
-
i
,
length
)
for
i
in
range
(
length
-
1
)
:
swap
(
numList
,
1
,
length
-
i
)
# 由于大頂堆的堆頂元素是最大的，把它和數(shù)組最后的元素（堆的最下層最右元素）
# 進(jìn)行互換，就相當(dāng)于把最大值放在了最后，下一次，把最后一個(gè)元素撇出來，對剩下來的在排序
heapAdjust
(
numList
,
1
,
length
-
i
-
1
)
# 由于交換之前，已經(jīng)都調(diào)整為最大堆了，而交換之后，大部分都符合堆的規(guī)則，
# 只從堆頂元素（下標(biāo)為1）開始，只進(jìn)行局部的調(diào)整就好，
# 這時(shí)候不用再像剛開始構(gòu)建最大堆一樣從下往上，從右往左調(diào)整交換了。
return
[
numList
[
i
]
for
i
in
range
(
1
,
len
(
numList
)
)
]
numlist
=
[
50
,
16
,
30
,
10
,
60
,
90
,
2
,
80
,
70
]
print
(
heapSort
(
numlist
)
)
參考文章
有輔助元素的堆排序
https://www.cnblogs.com/chengxiao/p/6129630.html
https://www.cnblogs.com/onepixel/articles/7674659.html
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
