Go语言基于最大值的选择排序仅排序最后一个元素的问题排查与修复

问题表现 #

输入数组 []int{3,5,4,2,1} 后，输出结果为 [3,1,4,2,5]，仅最后一个元素是正确的全局最大值，前面的元素未完成排序。

错误原因分析 #

最常见的问题集中在两个核心逻辑上：

1. 未缩小最大值查找区间：标准的降序选择排序，需要每次在未排序的子数组中找最大值，再将其交换到未排序区间的末尾。如果你的代码每次都在整个数组中查找最大值，只会把全局最大值交换到最后一位，前面的元素不会被处理。
2. 外层循环逻辑错误：如果外层循环只执行了一次，或者没有从数组末尾逐步向前收缩未排序区间的边界，就会导致只有最后一个元素被正确放置。
3. Max 函数实现缺陷：如果 Max 函数没有接收区间边界参数，每次都返回整个数组的最大值索引，就会重复选中同一个最大值，无法处理前面的子数组。

修复方法与代码示例 #

以下是修正后的完整代码，核心是明确未排序区间的边界，并让 Max 函数仅在该区间内查找：

package main

import "fmt"

// Swap 交换数组中指定索引的两个元素
func Swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

// Max 返回[start, end]区间内最大值的索引（包含两端）
func Max(arr []int, start, end int) int {
	maxIdx := start
	for k := start + 1; k <= end; k++ {
		if arr[k] > arr[maxIdx] {
			maxIdx = k
		}
	}
	return maxIdx
}

// SelectionSortDesc 基于最大值的选择排序（降序）
func SelectionSortDesc(arr []int) {
	n := len(arr)
	// 外层循环：从数组末尾向前收缩未排序区间
	for i := n - 1; i > 0; i-- {
		// 在[0, i]的未排序区间内找最大值索引
		maxIdx := Max(arr, 0, i)
		// 将最大值交换到未排序区间的末尾（即当前i的位置）
		Swap(arr, maxIdx, i)
	}
}

func main() {
	arr := []int{3, 5, 4, 2, 1}
	SelectionSortDesc(arr)
	fmt.Println(arr) // 输出 [5,4,3,2,1]
}

关键修复点 #

• 外层循环边界：从数组最后一位 n-1 开始，逐步向前遍历到索引1，每次循环后未排序区间的末尾索引 i 减一，已排序的最大值不再参与后续查找。
• Max 函数的区间限制：新增 start 和 end 参数，确保每次只在未排序的子数组范围内查找最大值，避免重复选中全局最大值。
• 交换逻辑：每次将找到的最大值交换到当前未排序区间的末尾，逐步构建已排序的后缀。

内容的提问来源于stack exchange，提问作者natalia