选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，特别适合初学者理解排序的基本概念。它通过反复选择未排序部分中的最小元素并将其放置到已排序部分的末尾来实现排序。本文将详细讲解选择排序的原理、步骤，并提供C语言代码示例，帮助初学者快速上手。

原理

选择排序的核心思想是：

从数组的未排序部分找到最小（或最大）元素。
将这个最小元素与未排序部分的第一个元素交换。
将已排序部分的边界向右移动一位，缩小未排序部分的范围。
重复上述步骤，直到整个数组排序完成。

它的时间复杂度是 O(n²)，其中 n 是数组的长度。虽然在实际应用中效率不如快速排序或归并排序，但它的简单性使其成为学习算法的理想起点。

步骤

假设我们要对一个整数数组进行升序排序，以下是选择排序的详细步骤：

初始化：从数组的第一个元素开始，假设它是未排序部分的最小值。
寻找最小值：遍历未排序部分，找到最小元素的索引。
交换：将找到的最小元素与未排序部分的第一个元素交换。
更新范围：将已排序部分的边界向右移动一位（即未排序部分的起始位置加1）。
重复：对剩余的未排序部分重复步骤2-4，直到整个数组排序完成。

实现

下面是用C语言实现选择排序的代码，包含详细注释以帮助理解。

main.c
#include <stdio.h>

// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    
    // 外层循环：控制未排序部分的起始位置
    for (i = 0; i < n-1; i++) {
        // 假设当前未排序部分的第一个元素是最小的
        min_idx = i;
        
        // 内层循环：寻找未排序部分的最小元素
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j; // 更新最小元素的索引
            }
        }
        
        // 交换最小元素与未排序部分的第一个元素
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

// 打印数组的辅助函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数：测试选择排序
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组：");
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    printf("排序后的数组：");
    printArray(arr, n);
    
    return 0;
}

编译 & 运行
$ gcc -o bin/selection-sort main.c
$ bin/selection-sort 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90 
$ 

下面是用Go语言实现选择排序的代码，包含详细注释以帮助理解。

main.go
package main

import "fmt"

// selectionSort 实现选择排序
func selectionSort(arr []int) {
    n := len(arr)
    
    // 外层循环：控制未排序部分的起始位置
    for i := 0; i < n-1; i++ {
        // 假设当前未排序部分的第一个元素是最小的
        minIdx := i
        
        // 内层循环：寻找未排序部分的最小元素
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j // 更新最小元素的索引
            }
        }
        
        // 交换最小元素与未排序部分的第一个元素
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}

// printArray 打印数组内容
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // 示例数组
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("原始数组：")
    printArray(arr)
    
    selectionSort(arr)
    
    fmt.Print("排序后的数组：")
    printArray(arr)
}

$ gsk build -v
create selection-sort/bin/selection-sort-linux-amd64
$ ./bin/selection-sort-linux-amd64 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90

总结

选择排序核心是从未排序部分找出最小或最大值，将其放置到已排序部分的末尾来实现排序。

作者：afxcn

来源：https://zh.gostartkit.com/docs/algo/selection-sort

发表日期：2025年6月28日

原理​

步骤​

实现​

总结​

原理

步骤

实现

总结