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

作者 : 开心源码 本文共1510个字,预计阅读时间需要4分钟 发布时间: 2022-05-12 共126人阅读

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

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

算法过程

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

  1. 公告变量 index 并指定初始值为待排序集合第一个元素的下标,通过遍历待排序集合,比较并升级 index,若 index 指向不为待排序集合最后一个元素,则交换 index 指向的值和待排序集合最后一个元素;
  2. 标记待排序集合最后一个元素为已排序;
  3. 重复步骤 1,2,直到待排序集合只有一个元素

演示示例

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

初始状态为:

根据算法过程:

  • 步骤一, index 初始值设为 0,指向元素 6,从下标为 1 的元素开始,比较 index 指向的值 和 3,比较大小后,选择下一个元素,比较 index 指向的值 和 4,比较大小,直到选择 8,比较大小并升级 index 值为 6,即元素 8 的下标,依次遍历比较待排序集合后,若 index 值不为待排序集合的尾元素下标,则交换 index 指向的值和待排序集合的尾元素;
  • 步骤二,标记待排序集合中的最后一个元素为已排序,从待排序集合中移除该元素

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

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

  • 步骤一,index 初始值设为 0,指向元素 6,从下标为 1 的元素开始,比较 index 指向的值 和 3,比较大小后,选择下一个元素,比较 index 指向的值 和 4,比较大小,直到选择 8,比较大小并升级 index 值为 6,即元素 8 的下标,依次遍历比较待排序集合后,若 index 值不为待排序集合的尾元素下标,则交换 index 指向的值和待排序集合的尾元素;
  • 步骤二,标记待排序集合中的最后一个元素为已排序,从待排序集合中移除该元素

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



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

观察以上过程可知,每次排序后会有一个元素变为已排序,即有一个元素处于正确的位置上。所以 N 个元素的序列,经过 N-1 次排序后,则有 N?1 个元素处于已排序状态,则剩下的一个元素不再需要进行排序。

算法示例

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]
代码分析 :
  • 以上代码中,第一层循环为需要进行的迭代次数,元素个数为 N 的集合,最多需要 N-1 次迭代就可确定 N-1 个元素的位置,即完成排序;
  • 第二层循环为比较元素值升级 index 指向位置的操作,随着迭代次数的添加,待排序元素个数减少;
  • 每一次循环后,判断 index 指向的能否为待排序集合最后一个元素,若不是则交换元素值。

算法分析

在每一轮排序过程中,选择出极值后,是通过直接交换元素位置的方式生成已排序元素的,所以选择排序是一种非稳固排序。对于 N 个元素的序列,需要进行 N-1 次迭代才能完成排序,每一次都需要遍历比较待排序集中所有元从来确定极值位置,即第 i 次迭代,遍历的元素个数为 N-i。所以算法的比较复杂度为 O(n^2),交换复杂度为 O(n)

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

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 排序算法(二):选择排序

发表回复