排序算法(二):选择排序

选择排序算法维护一个待排序集合和一个已排序集合,每轮迭代,从待排序集合中选择一个最小(最大)元素,添加到已排序集合中,通过多次迭代,最终完成排序。

选择排序与上一章的 冒泡排序 很相似,两者都维护了待排序集合和已排序集合,每次迭代结束都会产生一个已排序元素。不同之处在于冒泡排序的极值元素是通过不断的比较和交换位置产生的,选择排序则是不断比较和一次交换位置产生,所以相对冒泡排序,性能上具有优势。

算法过程

以递增排序为例,初始集合即为待排序集合,已排序集合初始为空

  1. 声明变量

并指定初始值为待排序集合第一个元素的下标,通过遍历待排序集合,比较并更新

,若

指向不为待排序集合最后一个元素,则交换

指向的值和待排序集合最后一个元素;

  1. 标记待排序集合最后一个元素为已排序;
  2. 重复步骤 1,2,直到待排序集合只有一个元素

演示示例

初始状态:0 次排序 待排序集合:[6,3,4,0,2,1,8,5,9,7] 已排序集合:[]

初始状态为:

根据算法过程:

  • 步骤一,

初始值设为 0,指向元素 6,从下标为 1 的元素开始,比较

指向的值 和 3,比较大小后,选择下一个元素,比较

指向的值 和 4,比较大小,直到选择 8,比较大小并更新

值为 6,即元素 8 的下标,依次遍历比较待排序集合后,若

值不为待排序集合的尾元素下标,则交换

指向的值和待排序集合的尾元素;

  • 步骤二,标记待排序集合中的最后一个元素为已排序,从待排序集合中移除该元素

1 次排序后 待排序集合:[6, 3, 4, 0, 2, 1, 8, 5, 7] 已排序集合:[9]

根据算法过程步骤三,待排序集合中不止一个元素,所以重复执行步骤一、二:

  • 步骤一,

初始值设为 0,指向元素 6,从下标为 1 的元素开始,比较

指向的值 和 3,比较大小后,选择下一个元素,比较

指向的值 和 4,比较大小,直到选择 8,比较大小并更新

值为 6,即元素 8 的下标,依次遍历比较待排序集合后,若

值不为待排序集合的尾元素下标,则交换

指向的值和待排序集合的尾元素;

  • 步骤二,标记待排序集合中的最后一个元素为已排序,从待排序集合中移除该元素

2 次排序后 待排序集合:[6, 3, 4, 0, 2, 1, 7, 5] 已排序集合:[8, 9]

... ... ...

9 次排序后 待排序集合:[0] 已排序集合:[1, 2, 3, 4, 5, 6, 7, 8, 9]

观察以上过程可知,每次排序后会有一个元素变为已排序,即有一个元素处于正确的位置上。所以

个元素的序列,经过

次排序后,则有

个元素处于已排序状态,则剩下的一个元素不再需要进行排序。

算法示例

def selectionSort(arr):
    for i in range(1, len(arr)):  # 迭代次数
        index = 0
        for j in range(1, len(arr) - i + 1):  # 遍历比较待排序集合中的元素
            if arr[index] < arr[j]:
                index = j
        if not index == j:
            arr[index],arr[j] = arr[j],arr[index]
代码分析 :
  • 以上代码中,第一层循环为需要进行的迭代次数,元素个数为

的集合,最多需要

次迭代即可确定

个元素的位置,即完成排序;

  • 第二层循环为比较元素值更新

指向位置的操作,随着迭代次数的增加,待排序元素个数减少;

  • 每一次循环后,判断

指向的是否为待排序集合最后一个元素,若不是则交换元素值。

算法分析

在每一轮排序过程中,选择出极值后,是通过直接交换元素位置的方式生成已排序元素的,所以选择排序是一种非稳定排序。对于

个元素的序列,需要进行

次迭代才能完成排序,每一次都需要遍历比较待排序集中所有元素来确定极值位置,即第

次迭代,遍历的元素个数为

。所以算法的比较复杂度为

,交换复杂度为

算法执行过程中,不需要申请额外的序列空间来保存临时元素,属于原地排序方式,所以算法的空间复杂度为

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一“技”之长

深入理解JavaScript函数 原

    从功能上理解,函数是一组可以随时运行的语句,是一段代码块,也是所谓的子程序。在JavaScript中,函数实质上也是一种对象,是Function对象。函...

7410
来自专栏前端杂货铺

new的探究

new操作符易用,但是往往容易忽略对其的理解。 var foo= new Foo(); 这个简单的语句,涉及到了一系列的步骤:   1),给对象开辟内存,即 v...

358110
来自专栏后端技术探索

当一只程序员遇到了一道无聊的智力填数题!

本猿在朋友圈和群里多次看到这样一道智力题(见下图),一看就是一道需要乱扯的无聊的题目。好吧,试试就试试。

9210
来自专栏编程

Python基础知识2:字典

字典一种key - value 的数据类型,就像上学用的字典通过拼音查找汉字一样;字典是Python语言中唯一的映射类型。字典对象是可变的,它是一个容器类型,能...

265100
来自专栏测试开发架构之路

C和指针小结(C/C++程序设计)

C和指针 相关基础知识:内存的分配(谭浩强版) 1、整型变量的地址与浮点型/字符型变量的地址区别?(整型变量/浮点型变量的区别是什么) 2、int *p,指向整...

345110
来自专栏微信公众号:Java团长

浅谈Java中的equals和==

  为什么第4行和第5行的输出结果不一样?==和equals方法之间的区别是什么?如果在初学Java的时候这个问题不弄清楚,就会导致自己在以后编写代码时出现一些...

9810
来自专栏机器学习算法与Python学习

python: sort, sorted, reverse

python语言中的列表排序方法有三个:reverse反转/倒序排序、sort正序排序、sorted可以获取排序后的列表。在更高级列表排序中,后两中方法还可以加...

39480
来自专栏技术碎碎念

python3 入门 (四) 类与继承

Python 类 Python中的类提供了面向对象编程的所有基本功能:类的继承机制允许多个基类,派生类可以覆盖基类中的任何方法,方法中可以调用基类中的同名方法。...

436120
来自专栏微信公众号:Java团长

浅谈Java中的equals和==

  为什么第4行和第5行的输出结果不一样?==和equals方法之间的区别是什么?如果在初学Java的时候这个问题不弄清楚,就会导致自己在以后编写代码时出现一些...

10430
来自专栏java一日一条

浅谈Java中的equals和==

为什么第3行和第4行的输出结果不一样?==和equals方法之间的区别是什么?如果在初学Java的时候这个问题不弄清楚,就会导致自己在以后编写代码时出现一些低级...

7520

扫码关注云+社区

领取腾讯云代金券