选择排序

选择排序像冒泡排序一样，每趟只放置一个项目到正确的位置。

但是，通常情况下它执行的交换会比较少，因为它会立即将项目移动到数组的正确位置。

1、算法思想：选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

2、算法过程

示例（第一趟的排序过程）

原始序列：49、38、65、97、76、13、27、49

1）在进行选择排序过程中分成有序和无序两个部分，开始都是无序序列

结果：49、38、65、97、76、13、27、49

2）从无序序列中取出最小的元素13，将13同无序序列第一个元素交换，此时产生仅含一个元素的有序序列，无序序列减一

结果：{13、} {38、65、97、76、49、27、49}

3）从无序序列中取出最小的元素27，将27同无序序列第一个元素交换，此时产生仅两个元素的有序序列，无序序列减一

结果：{13、27、} {65、97、76、49、38、49}

4）从无序序列中取出最小的元素38，将38同无序序列第一个元素交换，此时产生含三个元素的有序序列，无序序列减一

结果：{13、27、38、} {97、76、49、65、49}

5）从无序序列中取出最小的元素49，将49同无序序列第一个元素交换，此时产生含四个个元素的有序序列，无序序列减一

结果：{13、27、38、49、} {76、97、65、49}

6）从无序序列中取出最小的元素49，将49同无序序列第一个元素交换，此时产生含五个元素的有序序列，无序序列减一

结果：{13、27、38、49、49、} {97、65、76}

7）从无序序列中取出最小的元素65，将65同无序序列第一个元素交换，此时产生含六个元素的有序序列，无序序列减一

结果：{13、27、38、49、49、65} {97、76}

8）从无序序列中取出最小的元素76，将76同无序序列第一个元素交换，此时产生含七个元素的有序序列，无序序列减一

结果：{13、27、38、49、49、65、76、} {97}

9）最后一个元素肯定是最大元素，无序排序直接生产一个有序的序列

结果：{13、27、38、49、49、65、76、97

for(int i = 0; i < n-1;i++){//升序排列
    int temp = a[i]; //默认第一个元素最小
    int index = i;　　//记录该元素下标

    for(int j = i+1;j < n; j++)//从第i元素之后一个元素，开始遍历寻找比i元素更小的元素
        if(temp>a[j]){　　//如果满足条件
            temp = a[j];　//记录该元素值　
            index = j;　　//记录该元素下标
        }
    a[index] = a[i];　　//将初始元素i的值赋给找到的最小元素
    a[i] = temp;　　//将最小元素的值赋给下标最小的初始元素
}

 测试代码如下：

#include<iostream>
using namespace std;
const int n = 8;

int main()
{
    int a[n] = {  49,38,65,97,76,13,27,49};
    for(int i = 0; i < n-1;i++){
        int temp = a[i]; 
        int index = i;
        
        for(int j = i+1;j < n; j++)
            if(temp>a[j]){
                temp = a[j];
                index = j;
            }
        a[index] = a[i];
        a[i] = temp;
    }
    for(int i = 0;i < n;i++)
    cout<<a[i]<<"\t";
    return 0;
}