用Go语言实现插入排序算法
今天继续来写排序算法,这次是插入排序。先了解什么叫插入,书籍中说的是“把一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表”。教科书就是教科书,说话都说的稀里糊涂,怪不得那么多人学校都学不好数据结构和算法这门课。。。垃圾教编。
抛开书本,插入排序的重点在于插入,那插入的标准是什么?或者我们应该在什么情况需要把遍历的记录值插入进去?首先,我一次给你一个数字让你按照大小顺序来填入空格,第一次给你一个8,第二次给你一个2,虽然给的顺序是8-2,但你会把2插入到8的前面。也就是说我们从第一张牌开始就设定了拿到牌后都是有序的,拿牌前你都不知道他到底是什么顺序。这里就有了两个概念,一个是拿牌后的有序序列,一个是未拿牌的待排序序列,按照待排序列的顺序一张张的拿牌,拿到的记录我们称之为current,然后跟有序序列的每一个记录作比较,如果记录大于current,就把这个记录往后挪一格。这就是插入排序的实现思路,下面我们上代码:
package main
import (
"fmt"
)
func main() {
var array = [7]int{1,7,4,2,5,3,10}
sortByInsert(array[:])
// 打印
fmt.Println(array)
}
// 插入排序
func sortByInsert(nums []int) {
for i := 1;i<len(nums);i++{ // 默认下标为0的记录有序,所以从1开始遍历
j := i-1
current := nums[i]
for j >= 0 && nums[j] > current { // 有序序列从后往前遍历,挪动一格
nums[j+1] = nums[j]
j--
}
nums[j+1] = current
}
}
这部分就是插入排序的算法思路了,有问题请私聊哈。