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

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

简单选择排序是《数据结构》排序算法中一种,关于其稳定性的说法,前几版的教材一直让学生不明白怎么判断,直到严蔚敏老师的新版《数据结构》(人民邮电出版社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;

}

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180619G1J3N700?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券