常用12大排序算法之六:直接选择排序算法(基本思想+具体步骤+复杂度)

2017-04-22 18:19 阅读 4,563 次 评论 0 条

1.直接选择排序的基本思想

N个元素,每次挑出最大或者最小,执行(n-1)次循环。实际上选择排序是最简单的一种排序算法,因为它的思想非常朴素,每趟都选出剩余中最大或者最小的排在已经排好的数据后面。

 

2.直接选择排序的具体步骤

从待排序序列中,找到关键字最小的元素;
如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
从余下的 N - 1 个元素中,找出关键字最小的元素,重复1,2步,直到排序结束。

直接插入排序示意图

3.直接选择排序分析

(1)时间复杂度

直接选择排序的排序码比较次数KCN 与整个待排序对象序列象的初始排列无关。KCN=∑n−2i=0(n−i−1)=n(n−1)2。

移动次数:最好的时候为0;最坏的时候为3(n−1);

说明一下:基本上所有的排序算法最后的时候都是对应着已经完全排好序了,而最坏的时候通常都是反序排列。

所以,综合以上,简单排序的时间复杂度为 O(N2)。

(2)空间复杂度

简单选择排序需要占用一个临时空间,在交换数值时使用。

(3)特点

a.对于大数据表效率不高;

b.简单;

c.重复执行相同的工作,并没有从上一次的迭代中学到任何有助于的排序的知识。

d.移动次数可能是排序算法中比较好的了。如果采用in-place的数据交换方法,选择排序数据项的移动次数就一直为0。

e.不是一个稳定排序(从给的图示就可以看出)

单纯从每趟的效果上看,选择排序挑选最大或最小与冒泡算法有点类似,都是将剩下中的最大最小排起来,唯一的区别是冒泡算法是临近的两个数据项如果逆序就会交换,而选择排序不进行交换,只是在选定最值后进行交换。因此选择排序实际上并没有学到什么东西,每次迭代就是为了排好一个。而冒泡排序通过逆序的两个两两交换能够使得最值冒出来,而且还能实现未排序部分的初排序,最后能够通过判定是否发生交换提前终止迭代。

 

4.直接选择排序算法C语言源代码

 

5.直接选择排序算法C++源代码

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用12大排序算法之六:直接选择排序算法(基本思想+具体步骤+复杂度) | 算法君

发表评论


表情