??? 直接插入排序（Straight Insertion Sort）也稱“簡單插入排序”

??? 基本思想：第i趟排序將序列中第i+1個元素K_i+1插入到一個已經按值有序的子序列（K₁，K₂...K_i）中的合適的位置，使得插入后的序列仍然保持按值有序

??? 舉例分析：設有一個數據元素序列{3,6,4,2,11,10,5}，要求按從小到大順序排列，排序步驟如下圖所示：

???

??? 從上圖可知：一個包含N個元素的序列，需要N-1趟的直接插入排序就可以將原序列排列有序，代碼如下所示(C#實現):

1 public int[] SortByStraightInsertion(int[] m_SourceArray) 2 { 3 int tmpNum, j; 4 for (int i = 1; i < m_SourceArray.Length; i++) 5 { 6 tmpNum = m_SourceArray[i]; 7 j = i - 1; 8 //將tmpNum從已是有序的序列后端開始比較 9 //如果tmpNum小于后端數，那后端的數要順移 10 while (j >= 0 && tmpNum < m_SourceArray[j]) 11 { 12 m_SourceArray[j + 1] = m_SourceArray[j--]; 13 } 14 //將tmpNum插入到指定位置 15 m_SourceArray[j + 1] = tmpNum; 16 } 17 return m_SourceArray; 18 }

???? 算法分析：直接插入排序屬于穩定的排序，時間復雜度為：O(N²)，?空間復雜度：O(1)????

?

　　

轉載于:https://www.cnblogs.com/Hua-Min/p/StraightInsertionSort.html

總結

以上是生活随笔為你收集整理的排序算法（1）—直接插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。