Go语言数据结构之插入排序示例详解

插入排序

插入排序，英文名（insertion sort）是一种简单且有效的比较排序算法。

思想： 在每次迭代过程中算法随机地从输入序列中移除一个元素，并将改元素插入待排序序列的正确位置。重复该过程，直到所有输入元素都被选择一次，排序结束。

插入排序有点像小时候我们抓扑克牌的方式，如果抓起一张牌，我们放在手里；抓起第二张的时候，会跟手里的第一张牌进行比较，比手里的第一张牌小放在左边，否则，放在右边。

因此，对所有的牌重复这样的操作，所以每一次都是插入最正确的排序顺序，直到牌抓完为止。

动画演示

假设我们需要从小到大进行排序，动画演示如下：

Go 代码实现

package main
import "fmt"
func main() {
   arrays := []int{6, 2, 5, 8, 9, 3, 1}
   length := len(arrays)
   insertionSort(arrays, length)
   for i := 0; i < length; i++ {
       fmt.Printf("％d ", arrays[i])
   }
}
func insertionSort(unsorted []int, length int) {
   for i := 0; i < length; i++ {
       var insertElement = unsorted[i]
       var insertPosition = i
       for j := insertPosition - 1; j >= 0; j-- {
           if insertElement < unsorted[j] {
               unsorted[j+1] = unsorted[j]
               insertPosition--
           }
       }
       unsorted[insertPosition] = insertElement
   }
}

运行结果：

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\main.go"
1 2 3 5 6 8 9

来源：https://juejin.cn/post/7044021081933348894