选择排序

1. 基本思想

每次从未排序部分中查找到一个最小值，将其和未排序部分的第一个数进行交换，此时该数及其之前的数为有序状态，再对剩下的未排序部分的数进行选择排序。

2. 代码实现

void selectionSort(vector<int>& vec){
    for (int i = 0; i < vec.size(); i++){
        int min = i;
        for (int j = i + 1; j < vec.size(); j++) //查找最小值
            if (vec[j] < vec[min])
                min = j;
        swap(vec[min], vec[i]);
    }
}

3. 复杂度分析

• 在任何情况下比较次数为 (n - 1) + ... + 1，交换次数为 n ，所以时间复杂度为 O(n2)
• 同时该排序算法是稳定的