簡介

插入排序(Insertion Sort)是一種簡單直觀的排序算法。它的工作原理是：通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

算法實現(xiàn)步驟

從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序；

取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；

如果該元素（已排序）大于新元素，將該元素移到下一位置；

重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；

將新元素插入到該位置后；

重復(fù)步驟2~5。

Python 代碼實現(xiàn)# insertion_sort 代碼實現(xiàn)

from typing import List

def insertion_sort(arr: List[int]):

"""

插入排序

:param arr: 待排序List

:return: 插入排序是就地排序(in-place)

"""

length = len(arr)

if length <= 1:

return

for i in range(1, length):

value = arr[i]

j = i - 1

while j >= 0 and arr[j] > value:

arr[j + 1] = arr[j]

j -= 1

arr[j + 1] = value

# 測試數(shù)據(jù)

if __name__ == '__main__':

import random

random.seed(54)

arr = [random.randint(0,100) for _ in range(10)]

print("原始數(shù)據(jù)：", arr)

insertion_sort(arr)

print("插入排序結(jié)果：", arr)

# 輸出結(jié)果

原始數(shù)據(jù)： [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]

插入排序結(jié)果： [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]

動畫演示

算法分析

時間復(fù)雜度

如果數(shù)據(jù)初始是順序的，只需要外循環(huán)n-1次，每次進(jìn)行一次比較，無需移動元素，即可完成。所需的比較次數(shù)$C$和記錄移動次數(shù)$M$均達(dá)到最小值為：

$$

C_{\min}=n-1;

M_{\min}=0

$$

所以，插入排序最好的時間復(fù)雜度為$O\left( n \right)$。

如果數(shù)據(jù)初始是逆序的，則需要進(jìn)行$n-1$趟排序，每次排序中待插入的元素都要和$\left[ 0,i-1 \right]$中的$i$個元素進(jìn)行比較，并將這$i$個元素后移$i$次，每趟移動次數(shù)為$i+2$，此時比較和移動次數(shù)均達(dá)到最大值為：

$$

C_{\max}=1+2+3+\cdots +n-1=\frac{n\left( n-1 \right)}{2}=O\left( n^2 \right)

$$

$$

M_{\max}=2+3+4+\cdots +n=\frac{\left( n-1 \right) \left( n+2 \right)}{2}=O\left( n^2 \right)

$$

所以，平均時間復(fù)雜度為$O\left( n^2 \right)$。

空間復(fù)雜度

空間復(fù)雜度就是在交換元素時那個臨時變量所占的內(nèi)存空間，與數(shù)據(jù)規(guī)模無關(guān)，空間復(fù)雜度為$O\left( 1 \right)$

穩(wěn)定性

排序過程中，相同元素的相對位置保持不變，所以插入排序?qū)儆诜€(wěn)定排序。

綜合評價

聯(lián)系我們

總結(jié)

以上是生活随笔為你收集整理的python实现排序算法_python实现·十大排序算法之插入排序(Insertion Sort)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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