算法:插入排序
算法 About 1,508 words算法:插入排序
算法演进
将数组看作两个数组,前一部分为有序数组(已排好序),后一部分为无序数组(待排序)。
以[10, 20, 5, 0]
数组为例。
[10 20 5 0]
第 1 次排序 [10 20 5 0]
第 2 次排序 [5 10 20 0]
第 3 次排序 [0 5 10 20]
第一步
将[10]
看作有序数组,[20, 5, 0]
看作无序数组,无序数组的元素20
与它的前一位(有序数组的末位元素)比较。若比前一位大则将20
看作有序数组的末位元素;若比前一位小则与20
的前一位的前一位比较,以此类推。
第二步
将[10, 20]
看作有序数组,[5, 0]
看作无序数组,进行类似第一步的比较操作。
第三步
将[5, 10, 20]
看作有序数组,[0]
看作无序数组,进行类似第一步的比较操作,将0
插入到有序数组的最前面。
func InsertSortEvolution() {
arr := []int{10, 20, 5, 0}
// 将 [10] 看作有序数组,[20, 5, 0] 看作无序数组
insertVal := arr[1]
j := 1 - 1
for j >= 0 && insertVal < arr[j] {
arr[j+1] = arr[j]
j--
}
arr[j+1] = insertVal
log.Println("第1次排序", arr)
// 将 [10, 20] 看作有序数组,[5, 0] 看作无序数组
insertVal = arr[2]
j = 2 - 1
for j >= 0 && insertVal < arr[j] {
arr[j+1] = arr[j]
j--
}
arr[j+1] = insertVal
log.Println(arr)
log.Println("第2次排序", arr)
// 将 [5, 10, 20] 看作有序数组,[0] 看作无序数组
insertVal = arr[3]
j = 3 - 1
for j >= 0 && insertVal < arr[j] {
arr[j+1] = arr[j]
j--
}
arr[j+1] = insertVal
log.Println(arr)
log.Println("第3次排序", arr)
}
插入排序代码
arr := []int{10, 20, 5, 0}
log.Println(arr)
for i := 1; i < len(arr); i++ {
j := i
insertVal := arr[i] // 一定要使用临时变量接收,如果在循环中用 arr[i]获取,其实值已经变为移动后的值了
// 当前元素与前一个元素相比
for j-1 >= 0 && insertVal < arr[j-1] {
arr[j] = arr[j-1]
j--
}
arr[j] = insertVal
log.Println("第", i, "次排序", arr)
}
Views: 1,309 · Posted: 2021-02-07
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...