### **直接插入排序算法思想** 把待排序的紀錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的紀錄插入完為止，得到一個新的有序序列。 插入排序基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。 > 直接插入排序是由兩層嵌套循環組成的。外層循環標識并決定待比較的數值。內層循環為待比較數值確定其最終位置。直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續循環比較，直到找到比待比較數值小的并將待比較數值置入其后一位置，結束該次循環。 設無序數組為a\[0…n-1\]。 * 1.初始時，a\[0\]自成1個有序區，無序區為a\[1..n-1\]。 * 2.令i=1,將a\[i\]插入當前的有序區a\[0…i-1\]中形成a\[0…i\]的有序區間。 * 3.i++并重復第二步直到i==n-1，排序完成。 * * * ### **一趟直接插入排序方法** 具體做法： 將待插入記錄 a\[i\]的關鍵字從右向左依次與有序區中記錄 a[j]的關鍵字進行比較： * 1.若 a\[j\]的關鍵字大于 a\[i\]的關鍵字，則將 a\[j\]后移一個位置； * 2.若 a\[j\]的關鍵字小于或等于 a\[i\]的關鍵字，則查找過程結束，j+1 即為 a\[i\]的插入位置。 關鍵字比a\[i\]的關鍵字大的記錄均已后移，所以 j+1 的位置已經騰空，只要將 a\[i\] 直接插入此位置即可完成一趟直接插入排序。 例如待排序數組a\[0\]=8,a\[1\]=5,a\[2\]=10,a\[3\]=12,a\[4\]=7,a\[5\]=6 第一趟：a\[0\]=8，有序,a\[1...5\]無序。 第二趟：temp=5，a\[1\]=5 < a\[0\]=8, 8往后移一位，a\[1\]=8,a\[0\]=5,a\[0...1\]有序,a\[2...5\]無序。 第三、四趟：a\[2\]=10 > a\[1\]=8,a\[3\]=12 > a\[2\]=10，有序無須移動，a\[4...5\]無序。 第五趟：temp=7，a\[4\]=7 < a\[3\]=12,12往后移一位，a\[4\]=12，依次類推...直到a\[0\]=5 < temp，即a\[1\]=7。 第六趟類比第五趟，可以得到6插入位置為a\[1\]=6。排序完成。 * * * *直接插入排序算法時間復雜度：O(n^2)；空間復雜度：O(1)。直接插入排序是穩定的排序方法。*