//选择最小的整数，放在已经排序的整数序列的左边
//扫描选出最小的数的下标，标记出来，再把标记的数依次往前面排
//重点：选择排序选择最小的，往左边选，一次扫描，一次交换，
//与冒泡排序对比，冒泡排序在扫描过程中有很多次交换，一次扫描，最坏的情况下要交换n次

#include <iostream>
using namespace std;
void SelectSort(int *a,const int n);  //数组就是一个指针，常量n
int main() {
    int x[] = {1,3,5,7,9,0,2,4,6,8};
    SelectSort(x,10);
    for(int i=0;i<10;i++){
        cout << x[i]<<" ";
    }
    cout <<endl;
    return 0;
}
void SelectSort(int *list,const int n){
    for(int i=0;i<n;i++){  //也可以写成i<n-1
        int min = i; //min用来标记，初始化定义第一个数字是最小的,min是数组的下标，可以假设它为一个毛巾来理解
        for(int j=i+1;j<n;j++) {  //从i+1的元素开始扫描，从未排序的的数中找最小的下标
            if (list[j] < list[min])
                min = j;           //改变毛巾的位置
        }
        //一遍扫描结束后，进行交换
        swap(list[i],list[min]);  //直接使用C++内置的交换函数，把最小的数往前面放

    }
}