学步园

基本思想：第i趟在n-i+1(i=1,2,....,n-1)个记录中选取关键码最小的记录作为有序序列的第i个记录。

需要解决的问题？

（1）如何在待排序序列中选出关键码最小的记录？

（2）如何确定待排序序列中最小的记录在有序序列中的位置？

简单选择排序实质是一种交换排序，从待排序序列中选取最小的记录与待排序序列中的最后一个元素进行交换，从而实现一个自增长序列的排序。

因而简单选择排序每进行一次扫描，都会选出待排序序列中最小的元素放入有序序列。有序序列中的任何一个元素都比待排序序列中的元素小。进行到第i次扫描时就会得到一个有i个记录组成的有序序列。这些记录在有序序列中的位置不会在后面的排序中发生变化。

因而，简单选择排序没进行一次选择排序都可以唯一确定一个记录在有序序列中的位置。

时间复杂度分析：

一个有n个记录组成的序列，需要进行n-1次扫描，第一次扫描（n-1）个记录，第二次（n-2）个记录……

因而时间复杂度为：n(n-1)/2              时间复杂度为O（n×n）级

空间复杂度：

需要一个临时空间存储 空间复杂度为：O(1)；

具体实现代码如下：

#include <iostream>

using namespace std;

void selectSort(int r[], int n){
    int i,index,j,temp;
    for(i=1; i<n; i++)//执行第i遍扫描操作
    {
        index = i;
        for(j=i+1; j<n; j++)//比较无序序列中的记录
        {
            if(r[index] > r[j])//记录序列中最小值的位置
            {
                index = j;
            }
        }
        if(index != i)//如果无序序列中第一个记录不是最小值，则进行交换
        {
            temp = r[index];
            r[index] = r[i];
            r[i] = temp;
        }
    }
}

int main()
{
    int r[]  = {0,5,6,8,4,9,6,74,65,123,94};
    int n = sizeof(r)/sizeof(r[0]);
    selectSort(r, n);
    for(int i=1; i<n; i++)
    {
        cout<<r[i]<<"  ";
    }
    return 0;
}