简单选择排序（选择排序）

1.数组简单实现
2.顺序表实现
3.算法分析
注：没法优化
　基本思想：
每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录

Screen Shot 2018-12-18 at 21.37.54.png

Screen Shot 2018-12-18 at 21.38.49.png

数组代码

#include<iostream>
using namespace std;
int main()
{
    int n=6,a[6]={21,25,49,25,16,8};//定义 n为整数，a为整数组
    for(int i=1,flag,min,j;i<=n-1;i++)      //趟数n-1
    {
        for(flag=i-1, min=a[flag],j=flag+1;j<=n-1;j++)  //比较次数n-i+1
        {
            if(min>a[j])
            {
                min=a[j];
                flag=j;
            }
        }
        if(flag!=i-1)
        {
            int t=a[i-1];
            a[i-1]=a[flag];
            a[flag]=t;
        }
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";//8 16 21 25 25 49
    return 0;
}

顺序表实现

void SelectSort(SqList &K)
 { 
    for (i=1; i<L.length; ++i)
    { //在L.r[i..L.length] 中选择key最小的记录
        k=i;     
        for( j=i+1;j<=L.length ; j++)
            if ( L.r[j].key <L.r[k].key) k=j; 
        if(k!=i)L.r[i]←→L.r[k];            
    }  
}