选择排序算法详解：原理、优化与复杂度分析

这里有个小细节：我们在交换前判断了 min_index != i。虽然不判断也能通过自交换完成，但加上这个判断能减少不必要的内存写入操作，稍微提升一点性能。

三、双向选择排序优化

标准版本每轮只确定一个最小值。我们可以优化一下：每轮同时确定最小值和最大值。将最小值放前端，最大值放后端，这样一趟下来就能处理两个元素，效率理论上翻倍。

void SelectSort_Optimized(int* a, int n) {
    int begin = 0;
    int end = n - 1;
    
    while (begin < end) {
        int mini = begin;
        int maxi = begin;
        
        // 遍历当前未排序区间 [begin, end]
        for (int i = begin + 1; i <= end; i++) {
            if (a[i] < a[mini]) mini = i;
            if (a[i] > a[maxi]) maxi = i;
        }
        
        // 交换最小值到 begin 位置
        Swap(&a[begin], &a[mini]);
        
        // 关键点：如果最大值原本就在 begin 位置，交换后它被移到了 mini 位置
        // 此时必须更新 maxi 的下标，否则下次交换会出错
        if (maxi == begin) {
            maxi = mini;
        }
        
        // 交换最大值到 end 位置
        Swap(&a[end], &a[maxi]);
        
        begin++;
        end--;
    }
}

特殊情况说明： 当最大值恰好位于 begin 位置时，第一次交换 Swap(&a[begin], &a[mini]) 会把最大值换到 mini 的位置。如果不更新 maxi 变量，第二次交换就会把错误的元素放到末尾。上面的代码通过 if (maxi == begin) 处理了这个边界情况。

四、时空复杂度分析

时间复杂度

无论最好、最坏还是平均情况，比较次数都是固定的。

• 第 1 趟：比较 n-1 次
• 第 2 趟：比较 n-2 次
• ...
• 总比较次数：(n-1) + (n-2) + ... + 1 = n(n-1)/2

因此，时间复杂度始终为 O(n²)。

空间复杂度

选择排序是原地排序（In-place），只需要常数级的辅助变量来存储下标和临时交换值，不需要额外开辟与数据规模成比例的空间。

因此，空间复杂度为 O(1)。

总结来说，选择排序实现简单，占用空间少，但在大数据量下性能不如快速排序或归并排序。不过作为理解排序思想的基础，它依然非常有价值。