一缺亮、什么是插入排序？
其實(shí)插入排序是十分簡單的排序方法庄蹋，類似于我們打撲克，每次抽牌之后插入到原有的牌中迷雪，讓他們始終保持有序限书。
二、為什么要講插入排序章咧？
插入排序是一種時間復(fù)雜度為O(n2)的排序算法倦西，排序100萬個整數(shù)就需要幾乎一個小時。我寫這篇博客的原因主要是看了《編程珠璣》講解插入排序時赁严，我作為一個新人扰柠，并沒有注意到的一些點(diǎn)粉铐。
三、正文
首先我們先用最簡單的方法實(shí)現(xiàn)插入排序卤档，同樣是用我最近正在學(xué)習(xí)的Go語言實(shí)現(xiàn)蝙泼。
func InsertSort(arr []int) {
for i := 1; i < len(arr); i++ { // 外循環(huán)
for (j = i; j > 0 && arr[j] < arr[j-1]; j--) { // 內(nèi)循環(huán)
arr[j], arr[j-1] = arr[j-1], arr[j]
}
}
}
然而一些語言的語法糖或者語言自帶庫函數(shù)有時候用起來會簡便，例如一些語言庫函數(shù)中有swap()函數(shù)用于交換劝枣，但是性能上未必是最好的汤踏。
arr[j], arr[j-1] = arr[j-1], arr[j]
上面的Go語言語句實(shí)際表現(xiàn)為：
tmp := arr[j]
arr[j] = arr[j-1]
arr[j-1] = tmp
我們發(fā)現(xiàn)，每次內(nèi)循環(huán)都會對tmp賦相同的初始值arr[i]舔腾，所以我們將tmp賦值語句移出內(nèi)循環(huán)溪胶，變?yōu)?/p>
func InsertSort(arr []int) {
for i := 1; i < len(arr); i++ { // 外循環(huán)
tmp := arr[i]
for (j = i; j > 0 && tmp < arr[j-1]; j--) { // 內(nèi)循環(huán)
arr[j] = arr[j-1]
}
x[j] = tmp
}
}
修改后的代碼在機(jī)器上運(yùn)行要比修改前快10%左右，提升雖然不大稳诚，但是在編碼中是我這種新人應(yīng)該關(guān)注的點(diǎn)哗脖。
（如有錯誤，歡迎指正）
