插入排序insertion sort

03-06

插入排序就是每一步都將一個待排數據按其大小插入到已經排序的數據中的適當位置，直到全部插入完畢。插入排序方法分

直接插入排序
折半插入排序

1. 直接插入排序

直接插入排序(Straight Insertion Sort)的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表。開始時有序表中只包含1個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，將它插入到有序表中的適當位置，使之成為新的有序表，重複n-1次可完成排序過程。

　　對於n個元素的記錄。　　第一趟　　：　　把第2個元素拿出來跟第1個元素對比，小的在前面、大的在後面。　　第二趟　　：　　把第3個元素拿出來插入到前2個元素中，使他們有序。　　第三趟　　：　　把第4個元素拿出來插入到前3個元素中，使他們有序。　　......　　第n-1趟　：　　把第n個元素拿出來插入到前n-1個元素中，排序完成。

1.1 圖解

1.2 代碼

def straight_insertion_sort(unsorted): 返回插入排序結果 Args: unsorted:未排序的list Return：排序的list if len(unsorted) <= 1: return unsorted size = len(unsorted) i = 1 while i <= size - 1: j = i while j > 0: if unsorted[j] < unsorted[j-1]: temp = unsorted[j-1] unsorted[j-1] = unsorted[j] unsorted[j] = temp j = j-1 else: break i = i + 1 return unsortedif __name__ == __main__: a = [1,4,3,2,-10,4,56] print straight_insertion_sort(a)

1.3 複雜度分析

對於大小為 $n$ 的未排序數據集，需要第一層遍歷從2到 $n$ ，然後在每一層里需要遍歷從1到 $j$ ，因此複雜度為

$T(n)=sum_{i=2}^{n}{sum_{j=1}^{i}{epsilon}}= heta(n^{2})$

2. 折半插入排序

折半插入排序是對直接插入排序的改進。

我們看直接插入排序的步驟簡單而言其實就2步，第1步是從已經排好序的數組中找到該插入的點，第2步是將數據插入，然後後面的數據整體後移。那麼直接插入排序是如何找到該插入的點的呢？是無腦式的從頭到尾的遍歷。問題是被插入的數組是排好序的，根本沒有必要從頭到尾遍歷。折半插入排序就是改進了第1步——從已經排好序的數組中找到該插入的點。

折半插入排序是怎麼做的呢？非常簡單。取已經排好序的數組的中間元素，與插入的數據進行比較，如果比插入的數據大，那麼插入的數據肯定屬於前半部分，否則屬於後半部分。這樣，不斷遍歷縮小範圍，很快就能確定需要插入的位置。這就是所謂「折半」。

2.1 代碼實現

def find_insert_point(sorted_list,x): 需要插入到begin的前面 begin = 0 end = len(sorted_list) - 1 while begin <= end: middle = (begin + end) / 2 if (sorted_list[middle] > x): end = middle - 1 else: begin = middle + 1 return begindef binary_insertion_sort(unsorted): 返回插入排序結果 Args: unsorted:未排序的list Return：排序的list if len(unsorted) <= 1: return unsorted size = len(unsorted) i = 1 while i <= size - 1: temp = unsorted[i] #對第j個元素進行排序 x = find_insert_point(unsorted[:i],unsorted[i]) # 往後排 j = i while j > x: unsorted[j] = unsorted[j-1] j = j - 1 unsorted[x] = temp i = i + 1 return unsorted if __name__ == __main__: a = [1,4,3,2,-10,4,56] print binary_insertion_sort(a)

2.2 演算法分析

折半插入排序的時間複雜度 $T(n)=sum_{i=2}^{n}{ heta(n)}= heta(n^{2})$

折半插入排序演算法是一種穩定的排序演算法，比直接插入演算法明顯減少了關鍵字之間比較的次數，因此速度比直接插入排序演算法快，但記錄移動的次數沒有變，所以折半插入排序演算法的時間複雜度仍然為 $heta(n^{2})$ ，與直接插入排序演算法相同。

折半插入排序是穩定的演算法，它滿足穩定演算法的定義。