算法:插入排序

算法 大约 1508 字

算法:插入排序

算法演进

将数组看作两个数组,前一部分为有序数组(已排好序),后一部分为无序数组(待排序)。

[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)
}
阅读 36 · 发布于 2021-02-07

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批