简单选择排序

算法思想

基本思想

每次选择最小的数，放到对应的位置

详细解释

扫描一次未排序子数组，寻找最小的数，然后和未排好序的子数组的第一个元素交换位置，也就是每轮将最小的数字放到未排好序的部分的最前面刚好和插入排序相反，选择排序是向后寻找最小的数字，移动到前面，但是每次移动到的目的地“前面”是会变化的，这个前面是会随着寻找到的最小数字向后移动的相当于直接就将数字放在了它该在的位置，这个数字也只用移动一次
它的每次移动只改变两个位置上的数字，其他数字都不移动
大致流程：

从待排序序列中，找到关键字最小的元素；
如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
从余下的 $N - 1$ 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

图像理解

图源：cuijiahua

其中黄色色块为已经拍好序的部分，在之后都不会移动它

时空间复杂度

时间复杂度

简单选择排序的比较次数与序列的初始排序无关。假设待排序的序列有 $n$ 个元素，则比较次数总是 $n(n - 1) / 2$。
而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.
当序列反序时，移动次数最多，为 $3N (N - 1) / 2$ 。
所以，综合以上，简单排序的时间复杂度为 $O(N^2)$ 。

空间复杂度

简单选择排序需要占用 1 个临时空间（temp），用于保存最小值得索引，所以为 $O(1)$

稳定性

不稳定

源代码

vector 更通用模板

#include <iostream>
#include <vector>
 
using namespace std;
 
// 简单选择排序
vector<int> SelectSort(vector<int> list){
    // 需要遍历获得最小值的次数
    // 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
    vector<int> result = list;
    for (int i = 0; i < result.size(); i++){
        // 用来保存最小值得索引
        int index = i;
        // 用来保存最小值得索引
        for (int j = i + 1; j < result.size(); j++){
            if (result[index] > result[j]){
                index = j;
            }
        }
        if (index == i){
            continue;
        }
        // 将找到的第i个小的数值放在第i个位置上
        swap(result[i], result[index]);
    }
    return result;
}
 
int main(){
    int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
    vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
    cout << "排序前" << endl;
    for (int i = 0; i < test.size(); i++){
        cout << test[i] << " ";
    }
        cout << endl;
    vector<int> result;
    result = SelectSort(test);
    cout << "排序后" << endl;
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << " ";
    }
}

数组简单理解

#include <iostream>

using namespace std;

void swap(int &a, int &b) //交换值
{
    int tmp = a;
    a = b;
    b = tmp;
}

void selectionsort()
{
    int a[] = {10, 8, 11, 7, 4, 12, 9, 6, 5, 3}; //?待排序数组

    int size = sizeof(a) / sizeof(int);
    int i, j, min_index;
    for (i = 0; i < size; i++) //?用来递增选择找到第i小的数字
    {
        min_index = i;                 //?用来记录目前的最小数字所在的下标位置
        for (j = i + 1; j < size; j++) //?向后遍历寻找未排序数组中最小的数
        {
            if (a[j] < a[min_index])
                min_index = j; //?找到了最小的数记录它的下标，便于之后的交换
        }
        swap(a[min_index], a[i]); //?交换数组
    }
    for (int i = 0; i < size; i++)
        cout << a[i] << " ";
}

int main()
{
    selectionsort();
}