基于Go语言实现选择排序算法及优化

不晚

发布时间：2026-10-15 | 2人浏览过

原创

选择排序是一种直观的比较排序算法，通过在未排序区间反复寻找最小（或最大）元素并交换至已排序末尾来完成排序。在Go语言中，该算法基础实现存在较多无效比较。本文通过代码演示如何从基础的单端查找优化为同时处理两端的“双向选择排序”，从而在保持O(N²)时间复杂度的前提下，成倍降低实际运行耗时。

选择排序原理

选择排序的核心逻辑是将数组分为“已排序”和“未排序”两部分。初始状态下，所有元素均位于未排序区。算法每次从未排序区间中找到最小（升序时）或最大（降序时）的元素，将其与未排序区的第一个元素交换位置，该元素随即进入已排序区。重复此过程直到未排序区间为空。

图片演示

第1步：基础选择排序实现

最直观的实现方式是使用单层循环控制每一轮的开始位置 i，内层循环遍历剩余元素寻找最小值的索引 minPos，最后进行一次交换操作。

import "fmt"

func main() {
    nums := [8]int{8, 2, 3, 1, 6, 5, 7, 4}
    fmt.Println("原数组：", nums)
    fmt.Println("--------------------------------")
    SelectionSort(nums)
}

func SelectionSort(nums [8]int) {
    for i := 0; i < len(nums)-1; i++ {
        minPos := i
        // 内层循环寻找当前轮次的最小值下标
        for j := i + 1; j < len(nums); j++ {
            if nums[minPos] > nums[j] {
                minPos = j
            }
        }
        // 将找到的最小值交换到位置 i
        nums[i], nums[minPos] = nums[minPos], nums[i]
        fmt.Printf("第 %d 轮后：%v\n", i+1, nums)
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组：", nums)
}

执行结果：

原数组： [8 2 3 1 6 5 7 4]
--------------------------------
第 1 轮后：[1 2 3 8 6 5 7 4]
第 2 轮后：[1 2 3 8 6 5 7 4]
第 3 轮后：[1 2 3 8 6 5 7 4]
第 4 轮后：[1 2 3 4 6 5 7 8]
第 5 轮后：[1 2 3 4 5 6 7 8]
第 6 轮后：[1 2 3 4 5 6 7 8]
第 7 轮后：[1 2 3 4 5 6 7 8]
--------------------------------
排序后的数组： [1 2 3 4 5 6 7 8]

关键参数说明：

i：表示当前未排序部分的起始位置，也是本轮最小值应该存放的目标位置。
minPos：记录当前未排序区间内最小元素的索引，默认初始值为 i。
j：遍历指针，从 i + 1 开始向后扫描，更新 minPos。

该算法每次外层循环只确定了一个位置的最终值，需要进行 $N-1$ 轮比较。由于无论数组是否已经有序，都会执行完整的比较流程，且不存在提前终止机制，其最佳、最差及平均时间复杂度均为 O(N²)。

第2步：双向选择排序优化

基础算法的缺点是每轮仅移动一个元素。我们可以利用一次遍历找到未排序区间的最小值和最大值，分别放置到区间的头部和尾部。这样每轮可以确定两个元素的正确位置，从而将外层循环的迭代次数减半，虽然渐进时间复杂度不变，但常数因子显著减小。

import (
    "fmt"
)

func main() {
    nums := [4]int{3, 1, 4, 2}
    fmt.Println("原数组：", nums)
    fmt.Println("--------------------------------")
    SelectionSort(nums)
}

func SelectionSort(nums [4]int) {
    left := 0
    right := len(nums) - 1
    
    // 当左右指针相遇或交错时结束
    for left <= right {
        minPos := left
        maxPos := left
        
        // 单次遍历同时寻找当前区间的最大最小值下标
        for i := left + 1; i <= right; i++ {
            if nums[minPos] > nums[i] {
                minPos = i
            }
            if nums[maxPos] < nums[i] {
                maxPos = i
            }
        }
        
        // 1. 交换最小值到左侧
        nums[left], nums[minPos] = nums[minPos], nums[left]
        
        // 2. 关键修正：如果最大值原本就在 left 位置
        // 那么上一步它将 minPos 的值换走了，导致 maxPos 指向的不是真正的最大值了
        if maxPos == left {
            maxPos = minPos
        }
        
        // 3. 交换最大值到右侧
        nums[right], nums[maxPos] = nums[maxPos], nums[right]
        
        fmt.Printf("第 %d 轮后：%v\n", left+1, nums)
        
        // 左右边界向中间收缩
        left++
        right--
    }
    fmt.Println("--------------------------------")
    fmt.Println("排序后的数组：", nums)
}

执行结果：

原数组： [8 2 3 1 6 5 7 4]
--------------------------------
第 1 轮后：[1 2 3 4 6 5 7 8]
第 2 轮后：[1 2 3 4 6 5 7 8]
第 3 轮后：[1 2 3 4 5 6 7 8]
第 4 轮后：[1 2 3 4 5 6 7 8]
--------------------------------
排序后的数组： [1 2 3 4 5 6 7 8]

优化要点：

left 和 right：分别代表当前未排序区间的两端索引。
maxPos == left 判断：这是实现中最易出错的地方。因为在执行完最小值交换后，原 left 位置的元素被换到了 minPos。如果原先的最大值恰好在 left，此时它的下标应变为 minPos，否则后续交换最大值时会出现错误覆盖。

相比第一种方法，第二种方法在一次 for 循环中完成了一次比较并更新了两次状态，整体扫描次数减少了约一半。但在大数据量下，两者都属于平方级复杂度算法，性能差异主要体现在常数级别。