9.4.1 简单选择排序算法

简单选择排序法（Simple Selection Sort）就是通过n－i次关键字间的比较，从n－i＋1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之。

我们来看代码。

/* 对顺序表L作简单选择排序 */  
void SelectSort（SqList *L）  
{  
int i,j,min;  
for（i=1;i<L->length;i++）  
{  
min = i; /* 将当前下标定义为最小值下标 */  
for （j = i+1;j<=L->length;j++）/* 循环之后的数据 */  
{  
if （L->r[min]>L->r[j]） /* 如果有小于当前最小值的关键字 */  
min = j; /* 将此关键字的下标赋值给min */  
}  
if（i!=min） /* 若min不等于i，说明找到最小值，交换 */  
swap（L,i,min）; /* 交换L->r[i]与L->r[min]的值 */  
}  
} 

代码应该说不难理解，针对待排序的关键字序列是{9,1,5,8,3,7,4,6,2}，对i从1循环到8。当i=1时，L.r[i]=9，min开始是1，然后与j=2到9比较L.r[min]与L.r[j]的大小，因为j=2时最小，所以min=2。最终交换了L.r[2]与L.r[1]的值。如图9‐4‐1所示，注意，这里比较了8次，却只交换数据操作一次。

图9-4-1

当i=2时，L.r[i]=9，min开始是2，经过比较后，min=9，交换L.r[min]与L.r[i]的值。如图9‐4‐2所示，这样就找到了第二位置的关键字。

图9-4-2

当i=3时，L.r[i]=5，min开始是3，经过比较后，min=5，交换L.r[min]与L.r[i]的值。如图9‐4‐3所示。

图9-4-3

之后的数据比较和交换完全雷同，最多经过8次交换，就可完成排序工作。