插入排序

插入排序（英語(yǔ)：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

插入排序分析

def insert_sort(alist):# 從第二個(gè)位置，即下標(biāo)為1的元素開始向前插入for i in range(1, len(alist)):# 從第i個(gè)元素開始向前比較，如果小于前一個(gè)元素，交換位置for j in range(i, 0, -1):if alist[j] < alist[j-1]:alist[j], alist[j-1] = alist[j-1], alist[j]alist = [54,26,93,17,77,31,44,55,20] insert_sort(alist) print(alist)

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(n)
• 最壞時(shí)間復(fù)雜度：O(n2)
• 穩(wěn)定性：穩(wěn)定

希爾排序

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因DL．Shell于1959年提出而得名。 希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

希爾排序過程

希爾排序的基本思想是：將數(shù)組列在一個(gè)表中并對(duì)列分別進(jìn)行插入排序，重復(fù)這過程，不過每次用更長(zhǎng)的列（步長(zhǎng)更長(zhǎng)了，列數(shù)更少了）來進(jìn)行。最后整個(gè)表就只有一列了。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身還是使用數(shù)組進(jìn)行排序。

例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長(zhǎng)為5開始進(jìn)行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應(yīng)該看起來是這樣(豎著的元素是步長(zhǎng)組成)：

13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10

然后我們對(duì)每列進(jìn)行排序：

10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45

將上述四行數(shù)字，依序接在一起時(shí)我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。這時(shí)10已經(jīng)移至正確位置了，然后再以3為步長(zhǎng)進(jìn)行排序：

10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45

排序之后變?yōu)?#xff1a;

10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94

最后以1步長(zhǎng)進(jìn)行排序（此時(shí)就是簡(jiǎn)單的插入排序了）

希爾排序的分析

def shell_sort(alist):n = len(alist)# 初始步長(zhǎng)gap = n / 2while gap > 0:# 按步長(zhǎng)進(jìn)行插入排序for i in range(gap, n):j = i# 插入排序while j>=gap and alist[j-gap] > alist[j]:alist[j-gap], alist[j] = alist[j], alist[j-gap]j -= gap# 得到新的步長(zhǎng)gap = gap / 2alist = [54,26,93,17,77,31,44,55,20] shell_sort(alist) print(alist)

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：根據(jù)步長(zhǎng)序列的不同而不同
• 最壞時(shí)間復(fù)雜度：O(n2)
• 穩(wěn)定性：不穩(wěn)定

總結(jié)

以上是生活随笔為你收集整理的排序：插入排序与希尔排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。