选择排序算法详解与实现

双端优化版本

当前版本的选择排序在每轮遍历中仅能确定一个最小值。我们可以考虑对其进行优化，使每轮排序能同时确定最大值和最小值：将最小值置于数组前端，最大值置于末尾。通过这种双端选择的方式，可显著提升排序效率。

void SelectSort(int* a, int n) {
    // begin：存放一趟排序中选出的最小值
    int begin = 0;
    // end：存放一趟排序中选出的最大值
    int end = n - 1;
    
    while (begin < end) {
        // mini：指向未排序元素中的最小值的下标
        // maxi：指向未排序元素中的最大值的下标
        // 两者默认都初始化为 begin
        int mini = begin;
        int maxi = begin;
        
        // i 控制的逻辑：遍历未排序的数组元素
        for (int i = begin + 1; i <= end; i++) {
            if (a[i] < a[mini]) mini = i;
            if (a[i] > a[maxi]) maxi = i;
        }
        
        // 找到了最小值元素的下标，进行交换
        Swap(&a[begin], &a[mini]);
        
        // 特别注意：若 maxi 在 begin 位置上
        // 将 a[begin] 与 a[mini] 交换后，此时最大值的元素被换在了 mini 的位置
        // 所以此时 maxi 的下标要更新为 mini
        if (maxi == begin) {
            maxi = mini;
        }
        
        // 找到了最大值元素的下标，进行交换
        Swap(&a[end], &a[maxi]);
        
        begin++;
        end--;
    }
}

一般情况下的交换逻辑如下图所示：

特殊情况（如最大值恰好在 begin 位置）的处理逻辑如上代码注释所示。

复杂度分析

时间复杂度

无论最好、最坏还是平均情况，选择排序的时间复杂度都是 O(n^2)。

简单推导如下：

• 第 1 趟：从 n 个元素里找最小值，要比较 n−1 次
• 第 2 趟：从剩下的 n-1 个元素里找最小值，要比较 n−2 次
• ...
• 第 n-1 趟：比较 1 次

比较总次数为：(n−1) + (n−2) + ⋯ + 2 + 1 = n * (n - 1) / 2 故而时间复杂度为 O(n^2)。

空间复杂度

选择排序是原地排序，只需要常数个辅助变量（如保存当前最小值下标等），不需要额外开辟与 n 成比例的空间。 因此空间复杂度为：O(1)。