英文:
Quicksort implementation in Go
问题
我正在尝试在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)
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] 似乎没有更新
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
}
这是我之前用JavaScript编写的代码的直接翻译：
function quick_sort(arr) {
function partition(left, right, pivot) {
var v = arr[pivot];
swap(pivot, --right);
for (var i = left; i < right; i ++) {
console.log(arr, left, right, i, arr[i], v);
if (arr[i] <= v) {
swap(i, left++);
}
}
swap(left, right);
return left;
}
function swap(i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function recurse(left, right) {
if (left < right) {
var pivot = ~~((left + right) / 2)
pivot = partition(left, right, pivot);
recurse(left, pivot);
recurse(pivot + 1, right);
}
}
recurse(0, arr.length)
return arr;
}
var arr = [20, 43, 52, -1, 43, 29, 34];
console.log(quick_sort(arr));
在JavaScript中，它完美地工作，但是在Go中，我无法让它正常工作。由于某种原因，在我的分区函数中，在for循环中，arr[i]的值保持不变，即使i在变化。
我已经花了很多时间试图弄清楚我做错了什么，但是我无法找出原因。
有人看到我漏掉的东西吗？
英文:
I am trying to implement a quicksort algorithm in go just for learning purposes.
So far I have come up with the following code:
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
}
This is a direct translation of a code I had previously written in javascript:
function quick_sort(arr) {
function partition(left, right, pivot) {
var v = arr[pivot];
swap(pivot, --right);
for (var i = left; i < right; i ++) {
console.log(arr, left, right, i, arr[i], v);
if (arr[i] <= v) {
swap(i, left++);
}
}
swap(left, right);
return left;
}
function swap(i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function recurse(left, right) {
if (left < right) {
var pivot = ~~((left + right) / 2)
pivot = partition(left, right, pivot);
recurse(left, pivot);
recurse(pivot + 1, right);
}
}
recurse(0, arr.length)
return arr;
}
var arr = [20, 43, 52, -1, 43, 29, 34];
console.log(quick_sort(arr));
It works like a charm in js, but somehow I cannot get it to work in go. For some reason, in my partition function, in my for loop, the value of arr[i] remains constant even when i is changing.
I have spent quite a lot of time trying to figure out what I am doing wrong but I couldn't figure it out.
Does anyone see something I'm missing?
答案1
得分: 6
left++ 应该在 swap() 函数之后，如下所示：
if arr[i] <= v {
swap(i, left)
left++
}
修复后的输出为：
未排序：[20 43 52 -1 43 29 34]
排序后：[-1 20 29 34 43 43 52]
英文:
left++ should be after the swap() function as follow
if arr[i] <= v {
swap(i, left)
left++
}
After the fix, output is
Unsorted: [20 43 52 -1 43 29 34]
Sorted: [-1 20 29 34 43 43 52]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论