选择排序的基本思想是，在待排区段的记录序列中选出关键字最大或最小的记录，并将它移动到法定位置。第 i(i=1,2,…,n-1)趟的简单选择排序（序列中前 i-1 个记录的关键字均小于后 n-i+1 个记录的关键字）的作法是，在后 n-i+1 个记录中选出关键字最小的记录，并将它和第 i 个记录进行互换。如右图所示。
算法 10.12void SelectSort (SqList &L)
{
// 对顺序表L作简单选择排序
for (i=1; i<L.length; ++i) { // 选择第 i 小的记录，并交换到位
j = i;
for ( k=i+1; k<=L.length; k++ )
// 在L.r[i..L.length]中选择关键字最小的记录
if ( L.r[k].key < L.r[j].key ) j =k ;
if ( i!=j ) L.r[j] ←→L.r[i]; // 与第 i 个记录互换
}// for
} // SelectSort
无论待排序列处于什么状态，选择排序所需进行的"比较" 次数都相同，为
，而
"移动" 次数在待排序列为"正序" 时达最小为0，在 "逆序" 时达最大为 3(n-1)。
|
|||
|
选择排序是否也和插入排序或起泡排序相类似，在对"正序"和"逆序"的待排序列进行排序时，所需进行的"比较"和"移动"
次数有很大差别？
，而"移动"次数在待排序列为"正序"时达最小为0，在"逆序"时达最大为3(n-1)。