我决定在go中创建快速排序算法。
我的快速排序代码是:
package sorting
func QuickSort(input []int) []int {
if len(input) <= 1 {
return input
}
sorted := input
pivotIndx := len(sorted) - 1 // The index of the last item of the array
pivot := sorted[pivotIndx] // The value of the last item in the array
curLowIndx := 0
for indx, val := range sorted {
if val < pivot {
// Swap the items
sorted[indx], sorted[curLowIndx] = sorted[curLowIndx], sorted[indx]
// Increment the index on which the low position is stored.
// We need to do this so that the next item that is lower can be stored/swapped with the correct position
curLowIndx = curLowIndx + 1
}
}
sorted[curLowIndx], sorted[pivotIndx] = sorted[pivotIndx], sorted[curLowIndx]
// Sort the sub-arrays
QuickSort(sorted[:curLowIndx])
QuickSort(sorted[curLowIndx+1:])
return sorted
}
主文件的代码:
package main
import (
"fmt"
"github.com/.../.../sorting"
)
func main() {
// Sorting examples
toSort := []int{100, 20, 70, 30, 90, 40, 120, 123, 10, 23}
fmt.Println(toSort) // returns: [100 20 70 30 90 40 120 123 10 23]
shouldBeSorted := sorting.QuickSort(toSort)
fmt.Println(shouldBeSorted) // returns: [10 20 23 30 40 70 90 100 120 123]
fmt.Println(toSort) // ALSO returns: [10 20 23 30 40 70 90 100 120 123]
}
在我的主函数中,我在要排序的变量中有一个切片(toSort
)。我创建一个新变量,要在其中存储排序后的切片(shouldBeSorted
)。但是在这里,我发现了一些意料之外的东西。当我调用sorting.QuickSort(toSort)
时,它会对其进行排序,并将返回值分配给shouldBeSorted
变量,但是接下来,它还会使用toSort
的结果来更新sorting.QuickSort(toSort)
变量。
我已经阅读了go中指针的用法,在传递指针时会期望这种行为,但传递'regular'变量时不会期望这种行为。
所以我的实际问题是:为什么会这样?为什么更改toSort
变量?我做错了什么吗?还是这是预期的?为什么会这样?
旁注:递归发生时,它本身也会在QuickSort函数中发生相同的事情:
QuickSort(sorted[:curLowIndx]) QuickSort(sorted[curLowIndx+1:])
尽管我首先需要合并返回的切片,但显然它会更新原始排序的切片。
我决定在go中创建快速排序算法。我的快速排序代码是:包排序func QuickSort(input [] int)[] int {如果len(input)<= 1 {return input} ...
切片实际上是由具有元信息的结构和指向存储实际数据的连续内存位置的指针组成的。即使您通过值传递toSort,复制的元结构仍然引用相同的基础内存位置。这就是为什么toSort也被更改的原因。