<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Insert Sort - 插入排序 -------- #### 問題 用插入排序對長度為$$ n $$的無序序列$$ s $$進行排序。 #### 解法 本問題對無序序列$$ s $$進行升序排序，排序后$$ s $$是從小到大的。 將長度為$$ n $$的序列$$ s $$分為左右兩個部分$$ left $$和$$ right $$，$$ left $$是已序的，范圍為$$ s[0,k] $$，$$ right $$是未序的，范圍為$$ s[k+1,n-1] $$，其中$$ 0 \le k \lt n $$。對$$ right $$中最左邊的元素$$ x = s[k+1] $$，在$$ left $$部分中找到一個位置$$ i $$，滿足$$ s[i-1] \le x \le s[i] $$，也就是說$$ x $$可以夾在$$ s[i-1] $$和$$ s[i] $$之間。為了滿足$$ left $$的有序性，將$$ left $$中$$ s[i,k] $$部分的元素向右移動一個位置到$$ s[i+1,k+1] $$，將$$ x $$放置在原$$ s[i] $$的位置即可。 例如下圖中，$$ left $$部分為$$ s[0,5] $$，$$ right $$部分為$$ s[6,n-1] $$，$$ right $$最左邊的首部元素$$ x = s[6] = 41 $$，在$$ left $$部分中合適的插入位置為$$ i = 3 $$（$$ s[2] \le x \le s[3] $$）。  將$$ s[3,5] $$向右移動一位到$$ s[4,6] $$，將原$$ x $$移動到$$ s[3] $$，就完成了一次插入。  對于長度為$$ n $$的數組$$ s $$，將$$ left $$初始化為$$ s[0,0] $$，$$ right $$初始化為$$ s[1,n-1] $$。重復上面的插入操作，直到$$ right $$為空，這時$$ left $$部分即為已序的結果，算法結束。對長度為$$ n $$的序列$$ s $$，每一輪將$$ right $$中一個元素插入$$ left $$中的時間為$$ O(n) $$，總共需要$$ n $$輪操作，該算法的時間復雜度為$$ O(n^2) $$。 -------- #### 源碼 [InsertSort.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/InsertSort.h) [InsertSort.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/InsertSort.cpp) #### 測試 [InsertSortTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Sort/InsertSortTest.cpp)