4.希爾排序（縮小增量排序）
4.1 算法思想
希爾排序是插入排序的一種優(yōu)化，又稱(chēng)“縮小增量排序”，是直接插入排序算法的一種更高效的改進(jìn)版本。
希爾排序是把記錄
按下標(biāo)的一定增量分組
，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。
先取一個(gè)正整數(shù)d1
4.2 算法分析
希爾排序的時(shí)間復(fù)雜度與增量序列的選取有關(guān)，例如希爾增量時(shí)間復(fù)雜度為O(n2)，而Hibbard增量的希爾排序的時(shí)間復(fù)雜度為O( n^(3/2) )，希爾排序時(shí)間復(fù)雜度的下界是n*log2n。希爾排序沒(méi)有快速排序算法快 O(n(logn))，因此中等大小規(guī)模表現(xiàn)良好，對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。
Shell排序的執(zhí)行時(shí)間依賴(lài)于增量序列。
好的增量序列的共同特征：
① 最后一個(gè)增量必須為1；
② 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。
這種算法不需要額外的空間，時(shí)間復(fù)雜度為o(1)
4.3 算法過(guò)程
先將整個(gè)待排序的元素序列按照增量分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：
- 選擇一個(gè)增量序列t1，t2，…，tk，其中t1>t2>……>tk，tk=1；
- 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 次排序；
- 每次排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量為1 時(shí)，即把所有的元素進(jìn)行一個(gè)插入排序處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
4.4 python代碼
def
shellSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
gap
=
n
//
2
while
gap
>=
1
:
for
i
in
range
(
gap
,
n
)
:
# 把前gap個(gè)空出來(lái)，以便進(jìn)行各組之間的插入排序(插入排序也是把第一個(gè)元素空出來(lái)，當(dāng)成已經(jīng)排好序的序列)
tempindex
=
i
while
tempindex
>=
gap
and
numList
[
tempindex
-
gap
]
>
numList
[
tempindex
]
:
numList
[
i
-
gap
]
,
numList
[
tempindex
]
=
numList
[
tempindex
]
,
numList
[
tempindex
-
gap
]
tempindex
-=
gap
# 先把一個(gè)子序列中的元素排好序，某個(gè)子序列中的元素下標(biāo)之間的間隔為gap
gap
=
gap
//
2
return
numList
numlist
=
[
4
,
5
,
7
,
8
,
6
,
1
,
2
,
3
,
4
]
print
(
shellSort
(
numlist
)
)
# 輸出結(jié)果為：[1, 2, 3, 4, 4, 5, 6, 7, 8]
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
