go - Golang 代码 : insertion sort in 2nd pass? 中的未知错误

Question

我是 Go 的新手。我正在使用 go version go1.10.4 linux/amd64。我的目标是要求用户将单个整数输入附加到数组中并对其进行排序。我为此使用插入排序。程序需要在收到用户输入的 'X' 时退出。

这是我的代码:

package main

import (
    "fmt"
    "strconv"
    //  "sort"
)

func insertionSort(arr []int) []int {
    // Traverse through 1 to len(arr)
    for i, _ := range arr[1:] {
        key := arr[i]
        j := i - 1
        for {
            if j >= 0 && key < arr[j] {
                arr[j+1] = arr[j]
                j = j - 1
            } else {
                break
            }
        }
        arr[j+1] = key
    }

    return arr
}

func main() {
    s := make([]int, 0, 3)
    var x string
    for {
        fmt.Printf("Enter a number: ")
        fmt.Scan(&x)

        if x == "X" {
            break
        }

        xInt, _ := strconv.Atoi(x)
        fmt.Println(xInt)

        s = append(s, xInt)
        //sort.Ints(s)
        s = insertionSort(s)
        fmt.Printf("%v\n", s)
    }
    fmt.Printf("%v\n", s)
}

我得到以下输出:

Enter a number: 5
[5]
Enter a number: 4
[5 4]
Enter a number: 3
[4 5 3]
Enter a number: 2
[3 4 5 2]
Enter a number: 1
[2 3 4 5 1]
Enter a number: X
[2 3 4 5 1]

问题:

为什么它在第二遍中被排序？我的意思是它首先打印附加数组，然后为下一个元素打印前一个元素的排序数组。为什么？我在附加后进行排序，所以不应该是这种情况......

我从 here 获取(并从 Python 代码转换)插入排序代码

Answer 1

你的 for 循环是错误的。当你这样做时，for i,_ := range arr[1:]{ ，i 变为 0，而不是 1。您想从位置为 1 的第二个元素开始遍历数组，但是当您执行 arr[1:] 时，你的数组发生变化，变成一个少了一个元素的 slice ，你的索引最终还是 0。

要修复它，请检查您发布的页面中的 c++ 代码并实现对原始数组的长度进行操作的 for 循环。

range arr类似于 foreach在其他语言中，并且很难使用索引进行操作。

注意:我也检查了页面的python代码。它还有一个用于 python 代码的 for 循环。长话短说，使用range arr[1:]谨慎:)

修复:

for i, _ := range arr[1:] => for i:=1;i<len(arr);i++

它带有剧透标签，因为我不想窃取您修复错误的乐趣。