简单选择排序-阿里云开发者社区

开发者社区> 人工智能> 正文

简单选择排序

简介:

简单选择排序也叫作直接选择排序

基本思想:

每一趟在后面n-i+1个中选出关键字最小的记录,作为有序序列的第i个记录

(1)设待排序的记录存放在数组r[1…n ]中,第一趟从r[1]开始,通过n-1次比较,从n个记录中选出关键字最小的记录,记为r[k],交换r[1]和r[k].

(2)第二趟从r[2]开始,通过n-2次比较,从n-1个记录中选出关键字最小的记录,记为r[k],交换r[1]和r[k]。

(3)第i趟从r[i]开始,通过n-i次比较,从n-1+1个记录中选出关键字最小的记录,记为r[k],交换r[i]和r[k].

(4)经过n-1趟,排序完成。

这里写图片描述

void SelectSort(SqList &K)
{
//对顺序表L做简单选择排序
    for(i=1;i<L.length;++i)
{
//在L.r[i...L.length]中选择关键字最小的记录
     k=i;
     for(j=j+1;j<=L.length;j++)
     if(L.r[j].key<L.r[k].key)k=j;//k指向此趟排序中关键字最小的记录
     if(k!=i)
 {
     t=L.r[i];
     L.r[i]=L.r[k];//交换r[i]与r[k]
     L.r[k]=t;
}
}
}

算法分析

移动次数

  • 最好情况: 0

  • 最坏情况:3(n-1)

比较次数:1/2(n*n-n)

时间复杂度:O(n*n)

空间复杂度:O(1)

算法特点

            不稳定

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章