Golang中实现归并排序时遇到的问题

Golang中实现归并排序时遇到的问题 大家好。我能够用Python实现归并排序，然后决定尝试用Go来实现。下面的Go版本代码与Python代码几乎完全相同。但我似乎无法找出问题出在哪里。非常感谢任何帮助。

package main

import (
	"fmt"
)

func merge(left []uint8, right []uint8) []uint8 {
	var combined []uint8
	leftIndex, rightIndex := 0, 0
	for leftIndex < len(left) && rightIndex < len(right) {
		if left[leftIndex] < right[rightIndex] {
			combined = append(combined, left[leftIndex])
			leftIndex++
		} else {
			combined = append(combined, right[rightIndex])
			rightIndex++
		}
	}
	combined = append(left[leftIndex:len(left)], right[rightIndex:len(right)]...)
	return combined
}

func mergeSort(current []uint8) []uint8 {
	if len(current) < 2 {
		return current
	}
	m := int(len(current) / 2)
	return merge(mergeSort(current[0:m]), mergeSort(current[m:len(current)]))
}

func main() {
	unsorted := []uint8{8, 6, 3, 0, 4, 5, 3, 9, 2}
	fmt.Printf("%v\n", mergeSort(unsorted))
}

更多关于Golang中实现归并排序时遇到的问题的实战教程也可以访问 https://www.itying.com/category-94-b0.html

5 回复

检查合并函数中combined的最后一次追加操作

更多关于Golang中实现归并排序时遇到的问题的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


啊，我明白了，我实际上并没有把它追加回 combined… 嗯，谢谢！

是的，这是正确的。或者也可以分别将左和右追加到组合中，我可能会选择这种方式。

感谢 yah01… 我使用了这几行代码代替：

temp := append(left[leftIndex:len(left)], right[rightIndex:len(right)]...)
combined = append(combined, temp...)
return combined

你的归并排序实现中存在一个关键错误：在merge函数中，你错误地使用了切片追加操作。具体来说，combined = append(left[leftIndex:len(left)], right[rightIndex:len(right)]...)这一行会直接覆盖之前合并的结果，而不是追加剩余元素。

以下是修正后的代码：

package main

import (
	"fmt"
)

func merge(left []uint8, right []uint8) []uint8 {
	var combined []uint8
	leftIndex, rightIndex := 0, 0
	for leftIndex < len(left) && rightIndex < len(right) {
		if left[leftIndex] < right[rightIndex] {
			combined = append(combined, left[leftIndex])
			leftIndex++
		} else {
			combined = append(combined, right[rightIndex])
			rightIndex++
		}
	}
	// 修正：追加剩余元素到combined切片
	combined = append(combined, left[leftIndex:]...)
	combined = append(combined, right[rightIndex:]...)
	return combined
}

func mergeSort(current []uint8) []uint8 {
	if len(current) < 2 {
		return current
	}
	m := len(current) / 2
	return merge(mergeSort(current[:m]), mergeSort(current[m:]))
}

func main() {
	unsorted := []uint8{8, 6, 3, 0, 4, 5, 3, 9, 2}
	fmt.Printf("%v\n", mergeSort(unsorted))
}

主要修改：

  1. 将combined = append(left[leftIndex:len(left)], right[rightIndex:len(right)]...)改为两次独立的append调用
  2. 简化了切片表达式，使用left[leftIndex:]和right[rightIndex:]
  3. 在mergeSort函数中简化了切片操作，使用current[:m]和current[m:]

修正后的代码输出正确结果：[0 2 3 3 4 5 6 8 9]

回到顶部