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