简单选择排序-------零基础学数据结构

简单选择排序选择排序的基本思想是：从待排序的元素序列中选择关键字最小或最大的元素，将其放在已排序元素序列的最前面或最后面，其余的元素构成新的待排序元素序列，并从待排序元素序列中选择关键字最小的元素，将其放在已排序元素序列的最前面或最后面。依次类推，直到待排序元素序列中没有待排序的元素，选择排序结束。本节的主要学习内容包括两种常用的选择排序：简单选择排序和堆排序。

12.3.1 简单选择排序

简单选择排序的基本思想是：假设待排序的元素序列有n个，第一趟排序经过n-1次比较，从n个元素序列中选择关键字最小的元素，并将其放在元素序列的最前面即第一个位置。第二趟排序从剩余的n-1个元素中，经过n-2次比较选择关键字最小的元素，将其放在第二个位置。依次类推，直到没有待比较的元素，简单选择排序算法结束。

简单选择排序的算法描述如下。

void SelectSort(SqList *L,int n)

/*简单选择排序*/

{

int i,j,k;

DataType t;

/*将第i个元素的关键字与后面[i+1...n]个元素的关键字比较，将关键字最小的的元素放在第i个位置*/

for(i=1;i<=n-1;i++)

{

j=i;

for(k=i+1;k<=n;k++) /*关键字最小的元素的序号为j*/

if(L->data[k].key<L->data[j].key)

j=k;

if(j!=i) /*如果序号i不等于j，则需要将序号i和序号j的元素交换*/

{

t=L->data[i];

L->data[i]=L->data[j];

L->data[j]=t;

}

}

}