插入排序就這麼簡單

從上面已經講解了冒泡和選擇排序了，本章主要講解的是插入排序，希望大家看完能夠了解并手寫出插入排序的代碼，然後就通過面試了！如果我寫得有錯誤的地方也請大家在評論下指出。

來源百度百科：

插入排序的基本操作就是将一個資料插入到已經排好序的有序資料中，進而得到一個新的、個數加一的有序資料，算法适用于少量資料的排序，時間複雜度為O(n^2)。是穩定的排序方法。

将一個資料插入到已經排好序的有序資料中

将要排序的是一個亂的數組<code>int[] arrays = {3, 2, 1, 3, 3};</code>

在未知道數組元素的情況下，我們隻能把數組的第一個元素作為已經排好序的有序資料，也就是說，把<code>{3}</code>看成是已經排好序的有序資料

用數組的第二個數與第一個數(看成是已有序的資料)比較

如果比第一個數大，那就不管他

如果比第一個數小，将第一個數往後退一步，将第二個數插入第一個數去

用數組的第三個數與已是有序的資料<code>{2,3}</code>(剛才在第一趟排的)比較

如果比2大，那就不管它

如果比2小，那就将2退一個位置，讓第三個數和1比較

如果第三個數比1大，那麼将第三個數插入到2的位置上

如果第三個數比1小，那麼将1後退一步，将第三個數插入到1的位置上

....

從前兩趟排序我們可以摸出的規律：

首先将已排序的資料看成一個整體

一個數組是需要<code>n-1</code>趟排序的，總是用後一位跟<code>已排序的資料</code>比較(第一趟：第二位跟<code>已排序的資料</code>比，第二趟：第三位跟<code>已排序的資料</code>比）

用第三位和<code>已排序的資料</code>比，實際上就是讓第三位數跟兩個數比較，隻不過這兩個數是已經排好序的而已。而正是因為它排好序的，我們可以使用一個循環就可以将我們比較的資料插入進去

上面的代碼還缺少了一個條件：如果目前比較的資料比<code>已排序的資料</code>都要小，那麼<code>while</code>中的<code>arrays[i - 1]</code>會比0還要小，這會報錯的。

我們應該加上一個條件：<code>i&gt;=1</code>時才可以，如果<code>i=1</code>了下次再進去的時候就退出循環，讓目前資料插入到<code>[0]</code>的位置上

是以完整的代碼是這樣的：

二分查找插入排序的原理：是直接插入排序的一個變種，差別是：在有序區中查找新元素插入位置時，為了減少元素比較次數提高效率，采用二分查找算法進行插入位置的确定。

參考資料：http://www.cnblogs.com/heyuquan/p/insert-sort.html

C語言實作第一種方式:

C語言實作第二種方式:

測試代碼:

參考資料:

https://www.cnblogs.com/xiaoming0601/p/5862793.html

http://blog.csdn.net/jianyuerensheng/article/details/51254415

如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要擷取更多的Java資源的同學，可以關注微信公衆号:Java3y

更多的文章可往：文章的目錄導航