插入排序演算法描述

插入排序（Insertion Sort）是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

演算法描述

一般來說，插入排序都採用in-place在數組上實現。具體演算法描述如下：

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置
4. 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
5. 將新元素插入到該位置後
6. 重複步驟2~5

下面是黃哥寫的python代碼和golang代碼

python 插入排序

#coding:utf-8 """ 如何通過學習python學會編程 https://github.com/pythonpeixun/article/blob/master/python/how_to_learn_python.md 黃哥python遠程視頻培訓班 https://github.com/pythonpeixun/article/blob/master/index.md 黃哥python培訓試看視頻播放地址 https://github.com/pythonpeixun/article/blob/master/python_shiping.md 幫你完成從不會寫代碼到會寫代碼解決問題的過渡。 諮詢qq:1465376564 """ def insert_sort(lst): length = len(lst) for i in range(1, length): tmp = lst[i] for j in range(i-1, -1, -1): if lst[j] > tmp: lst[j+1] = lst[j] else: lst[j+1] = tmp break if lst[0] > tmp: lst[0] = tmp if __name__ == __main__: lst = [8, 2, 4, 1, 9, 20, 15, 6, 0] insert_sort(lst) print(lst)

golang插入排序代碼

package main import ( "fmt" ) func InsertSort(lst []int) { length := len(lst) for i := 1; i < length; i++ { tmp := lst[i] for j := i - 1; j >= 0; j-- { if lst[j] > tmp { lst[j+1] = lst[j] } else { lst[j+1] = tmp break } } // 這個地方有點小技巧，因為golang 中j是for循環作用域，所以 // 直接判斷第一個元素 if lst[0] > tmp { lst[0] = tmp } } } func main() { lst := []int{3, 8, 2, 9, 7, 12, 33, 6, 97, 48, 23} InsertSort(lst) fmt.Println(lst) }

c語言代碼

void insertion_sort(int arr[], int len) { int i, j; int temp; for (i = 1; i < len; i++) { temp = arr[i]; //與已排序的數逐一比較，大於temp時，該數向後移 for (j = i - 1; j >= 0 && arr[j] > temp; j--) //j循環到-1時，由於短路求值，不會運算array[-1] arr[j + 1] = arr[j]; arr[j+1] = temp; //被排序數放到正確的位置 } }

python 其它的2個版本

def insertion_sort(n): if len(n) == 1: return n b = insertion_sort(n[1:]) m = len(b) for i in range(m): if n[0] <= b[i]: return b[:i]+[n[0]]+b[i:] return b + [n[0]]def insertion_sort(lst): if len(lst) == 1: return for i in xrange(1, len(lst)): temp = lst[i] j = i - 1 while j >= 0 and temp < lst[j]: lst[j + 1] = lst[j] j -= 1 lst[j + 1] = temp

演算法複雜度

如果目標是把n個元素的序列升序排列，那麼採用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數減去(n-1)次。平均來說插入排序演算法複雜度為O(n2)。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小於千，那麼插入排序還是一個不錯的選擇。 插入排序在工業級庫中也有著廣泛的應用，在STL的sort演算法和stdlib的qsort演算法中，都將插入排序作為快速排序的補充，用於少量元素的排序（通常為8個或以下）。

點擊黃哥python培訓試看視頻播放地址

黃哥python遠程視頻培訓班

註：文字資源來源於維基百科

推薦閱讀：