简单选择排序算法的两种实现

简单选择排序算法的两种实现

简单选择排序是《数据结构》排序算法中一种，关于其稳定性的说法，前几版的教材一直让学生不明白怎么判断，直到严蔚敏老师的新版《数据结构》（人民邮电出版社2015.2）相对说的明白些，就选择排序本身来讲，它是一种稳定的排序方法，但有的算法描述表现出不稳定性。

1．基本思想

简单选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个作为第一个；（不必说是交换还是移动记录）第二趟从第二个数据开始向后扫描，选择最小的作为第二个；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

2．算法

voidSelectSort (ElemR[],intn )

{//对记录序列R[1..n]作简单选择排序。

for(i=1; i++i)

{//选择第i小的记录，并交换到位

j= SelectMinKey(R, i);

//在R[i..n]中选择关键字最小的记录

if(i!=j)R[i]←→R[j]; //与第i个记录交换

}

} // SelectSort

算法中if (i!=j)R[i]←→R[j];与第i个与第j个记录交换，是跨越式交换，所以是不稳定的，要实现稳定的话，移动只能依次往后移动。

代码为：

if(i!=j)

｛

a[0]=a[j];

for(k=j;k>i;k--)a[k]=a[k-1];

a[i]=a[0];

}

这样描述算法就是稳定的，所以说简单选择排序是稳定的。

3.链式结构

链式结构的引入在一定程度上解决顺序结构移动记录问题，在排序时更不要交换数据域，通过修改指针来实现排序，并保证了稳定性。

Status SortSelect(LinkList *L)

{

LinkListp,q,min;

intx;

p=L;

while(p->next)

{

x=p->next->data;

min=p->next;/*设最小结点*/

q=min;

if(q->next)

{/*在最小结点后有结点，找更小*/

while(q->next)

{

if(q->next->data

{

min=q;

x=q->next->data;

}

q=q->next;

}

q=min->next;

min->next=min->next->next;/*移出最小结点*/

q->next=p->next;/*插入序列最后*/

p->next=q;

}

p=p->next;

}

return0;

}