10.4选择排序—简单选择排序

选择排序主要是每一趟从待排序列中选取一个关键码最小的记录，也即第一趟从n 个记录中选取关键码最小的记录，第二趟从剩下的n-1 个记录中选取关键码最小的记录，直到整个序列的记录选完。这样，由选取记录的顺序，便得到按关键码有序的序列。

操作方法：第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；如此，第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，直到整个序列按关键码有序。

【算法10.9】
void SelectSort(S_TBL *s)
{ for(i=1；i<s->length；i++)
{ /* 作length-1 趟选取*/
for(j=i+1，t=i；j<=s->length；j++)
{ /* 在i 开始的length-n+1 个记录中选关键码最小的记录*/
if(s->elem[t].key>s->elem[j].key)
t=j； /* t 中存放关键码最小记录的下标*/
}
s->elem[t]<-->s->elem[i]； /* 关键码最小的记录与第i 个记录交换*/
}
}

从程序中可看出，简单选择排序移动记录的次数较少，但关键码的比较次数依然是1/2*n(n+1)，所以时间复杂度仍为O(n2)。