Go 中的快速排序实现

Question

我正在尝试在 go 中实现快速排序算法，仅用于学习目的。

到目前为止，我想出了以下代码：

package main

import (

    "fmt"

)

var arr = []int{20, 43, 52, -1, 43, 29, 34}

func main() {

    fmt.Println("Unsorted: ", arr)

    quick_sort(arr)

    fmt.Println("Sorted: ", quick_sort(arr))

}

func quick_sort(arr []int) []int {

    var recurse func(left int, right int)

    var swap func(i int, j int)

    var partition func(left int, right int, pivot int) int

    swap = func(i int, j int) {

        var temp = arr[i]

        arr[i] = arr[j]

        arr[j] = temp

    }

    partition = func(left int, right int, pivot int) int {

        v := arr[pivot]

        right--

        swap(pivot, right)

        for i := left; i < right; i++ {

            // arr[i] doesn't seem to be updating here

            fmt.Println(arr, left, right, i, arr[i], v)

            if arr[i] <= v {

                left++

                swap(i, left)

            }

        }

        swap(left, right)

        return left

    }

    recurse = func(left int, right int) {

        if left < right {

            pivot := (right + left) / 2

            pivot = partition(left, right, pivot)

            recurse(left, pivot)

            recurse(pivot+1, right)

        }

    }

    recurse(0, len(arr))

    return arr

}

它在 js 中就像一个魅力，但不知何故我无法让它在 go 中工作。出于某种原因，在我的分区函数中，在我的 for 循环中，arr[i]即使发生i变化， 的值也保持不变。

我花了很多时间试图弄清楚我做错了什么，但我无法弄清楚。

有没有人看到我遗漏的东西？

Answer 1

left++应该在swap()函数之后如下&nbsp; &nbsp;if arr[i] <= v {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; swap(i, left)&nbsp; &nbsp; &nbsp; &nbsp; left++&nbsp; &nbsp; }修复后，输出为Unsorted:&nbsp; [20 43 52 -1 43 29 34]Sorted:&nbsp; [-1 20 29 34 43 43 52]