选择排序

选择排序（Selection Sort）的核心思想是‌每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾‌。

算法原理

• 核心思想：将数组分为 已排序区间 和 未排序区间，每次从未排序区间中选择 最小元素，将其交换到已排序区间的末尾。
• 特点：每轮遍历确定一个元素的最终位置，交换次数少（最多交换 n-1 次）。
• 稳定性：不稳定排序（交换可能破坏相同元素的相对顺序）。

---

时间复杂度

场景	时间复杂度
最好情况	O(n²)
最坏情况	O(n²)
平均情况	O(n²)

---

代码实现

Golang 实现

package main

import "fmt"

func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIndex := i  // 记录未排序区间的最小元素索引
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        // 将最小元素交换到已排序区间的末尾
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    selectionSort(arr)
    fmt.Println("Sorted:", arr)  // Output: Sorted: [11 12 22 25 34 64 90]
}

Java 实现

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;  // 记录未排序区间的最小元素索引
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 将最小元素交换到已排序区间的末尾
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(arr);
        System.out.print("Sorted: ");
        for (int num : arr) {
            System.out.print(num + " ");  // Output: Sorted: 11 12 22 25 34 64 90 
        }
    }
}