爱华网直接选择排序的基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
#include <iostream>
using namespace std;
void selectsort(int array[],int length)
{
int i,j,k,temp;
for(i=0;i<length-1;i++)
{
k=i;
for(j=i+1;j<length;j++)
{
if(array[j]<array[k])
k=j;
}
temp=array[i];
array[i]=array[k];
array[k]=temp;
for(k=0;k<length;k++)
cout<<array[k]<<"";
cout<<endl;
}
}
int main()
{
inta[]={41,82,51,63,47,78,56,17,15,77,94};
selectsort(a,11);
}
运行结果：
[root@localhost sort]# make selectsort
g++ -c selectsort.cpp
g++ -o selectsort selectsort.o
[root@localhost sort]# ./selectsort
15 82 5163 47 7856 17 4177 94
15 17 5163 47 7856 82 4177 94
15 17 4163 47 7856 82 5177 94
15 17 4147 63 7856 82 5177 94
15 17 4147 51 7856 82 6377 94
15 17 4147 51 5678 82 6377 94
15 17 4147 51 5663 82 7877 94
15 17 4147 51 5663 77 7882 94
15 17 4147 51 5663 77 7882 94
15 17 4147 51 5663 77 7882 94
[root@localhost sort]#
算法分析
（1）关键字比较次数
无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：
n(n-1)/2=0(n2)
（2）记录的移动次数
当初始文件为正序时，移动次数为0
文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
直接选择排序的平均时间复杂度为O(n2)。
（3）直接选择排序是一个就地排序
（4）稳定性分析
直接选择排序是不稳定的
