資料結構與算法（插入排序算法）

插入排序

插入排序是一種簡單直覺的排序算法，他的工作原理是通過建構有序序列，對于未排序的資料，在已排序序列中從後向前掃描，找到相應位置插入。插入排序實作上，再從後向前掃描過程中，需要反複把已經排序的元素逐漸向後挪位，為新元素提供插入空間。

插入排序分析

以序列alist=[2,1,5,1,4,66,3,42,5,67,4]為例，插入排序原理如下：

首先将序列的第一個元素記為有序序列，其餘剩下元素為無序序列，将無序序列重的第一個元素與有序序列的元素相比，比如有序序列的元素為2，無序序列的第一個元素為1，那1與2比較，發現1小于2，則将1插入到有序序列中，且排在2的前面；

然後将剩餘無序列的中的第一個元素5，與有序序列[1,2]進行比較，首先将5與2比較，發現5是大于2的，因為2是有序序列中最大的一個元素，故可直接将5插入到有序序列的最後，形成新的有序序列[1,2,5]。

按照上述的步驟一次對無序序列部分與有序序列部分進行比較，然後插入到相應的位置，即可形成完整的有序序列。

代碼實作

代碼1

def insert_sort(alist):
	for i in range(1,len(alist)):
		for j in range(i,0,-1):
			if alist[j] < alist[j-1]:
				alist[j], alist[j-1] = alist[j-1], alist[j]
	return alist
           

時間複雜度為 O ( n 2 ) O(n^2) O(n2)

代碼2

def insert_sort(alist):
    #插入排序
    for i in range(1, len(alist)):
        while i >0:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break
    return alist
           

第二種實作形式對于初始序列為升序的序列，時間複雜度 O ( n ) O(n) O(n)