python/TangDou/LuoGuBook/L9_2_SelectSort.md

选择排序

一、前置知识

C++求整数数组长度的办法

int len = sizeof(a) / sizeof(int);

二、视频教程

三分钟搞定选择排序（图解+动画演示）

三、算法总结

算法思路

每次挑选最小的数和 未确定 的 首个数字 交换。

####　算法步骤

• 枚举每一个数字a[i]
  • 枚举$i$后面的所有数字，找出$i$后面所有数字中最小的数字。
  • 将找到的最小数字与$a[i]$交换

注：需要注意边界，第一层循环最多到$n-1$

四、代码实现

#include <bits/stdc++.h>

using namespace std;
//选择排序
int a[] = {4, 1, 9, 5, 1, 7, 2};
int main() {
    // C++求整数数组长度的办法
    int len = sizeof(a) / sizeof(a[0]);

    for (int i = 0; i < len - 1; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++)
            if (a[j] < a[min]) min = j;
        swap(a[i], a[min]);
    }

    for (int i = 0; i < len; i++) cout << a[i] << " ";
    return 0;
}

五、问题

$Q:$既然要找最小值，为什么不直接用$min$记录最小值，而是记录的是最小值对应的位置呢？ A:只记录最小值，确实可以把未确定的首个数字修改为最小值，但，首个数字就不知道放到哪里去了~