美文网首页
选择排序

选择排序

作者: 小吉头 | 来源:发表于2020-11-12 07:55 被阅读0次

关键点

  • 无序区,一开始都是无序区
  • 有序区,每次执行完有序区数量不断增大,无序区数量不断减小
  • 排序的趟数

每趟遍历从无序区第二个元素开始向后找到最小的元素,和第一个元素交换,使得有序区数量增加1

趟数和每趟无序区下标都从1开始:
第1趟开始:有序区数量0,无序区数量n,无序区中选择最小值的下标:下标1,下标2,下标3...,下标n
第2趟开始:有序区数量1,无序区数量n-1,无序区中选择最小值的下标: 下标2,下标3,下标4...,下标n
第3趟开始:有序区数量2,无序区数量n-2,无序区中选择最小值的下标: 下标3,下标4,下标5...,下标n
第4趟开始:有序区数量3,无序区数量n-3,无序区中选择最小值的下标: 下标4,下标5,下标6...,下标n
第 i 趟开始:有序区数量 i-1,无序区数量 n-(i-1)=n-i+1,无序区中选择最小值的下标:下标i,下标i+1,...,下标n

下标一般都是从0开始,趟数和每趟无序区下标都转换成从0开始:
第0趟开始:有序区数量0,无序区数量n,无序区中选择最小值的下标:下标0,下标1,下标2...,下标n-1
第1趟开始:有序区数量1,无序区数量n-1,无序区中选择最小值的下标: 下标1,下标2,下标3...,下标n-1
第2趟开始:有序区数量2,无序区数量n-2,无序区中选择最小值的下标: 下标2,下标3,下标4...,下标n-1
第3趟开始:有序区数量3,无序区数量n-3,无序区中选择最小值的下标: 下标3,下标4,下标5...,下标n-1
第 i 趟开始:有序区数量 i,无序区数量 n-i,无序区中选择最小值的下标: 下标i,下标i+1,...,下标n-1

代码实现

#时间复杂度O(n^2)
def select_sort(li):
    n = len(li)
    for i in range(n-1):#n个数,n-1趟
        min_pos = i #记录无序区最小值的位置,即无序区的第一个元素
        for j in range(i+1,n):#第i趟时,无序区范围:下标i,下标i+1,...,下标n-1,从无序区范围的第二个开始一直到最后一个,即i+1~n-1,即range(i+1,n)
            if li[j] < li[min_pos]:
                min_pos = j
        li[i], li[min_pos] = li[min_pos], li[i]

排序稳定性

源数据中相同的元素相对顺序保持不变,即稳定排序
3 3 1 5使用选择排序就是不稳定,第一个1和第二个1排序完相对顺序变了。冒泡是稳定排序。
挨个换的是稳定排序,不挨个换的是不稳定排序

相关文章

  • 算法-选择排序

    算 法:选择排序算法时间复杂度: 选择排序算法概述 选择排序伪代码 选择排序实现 选择排序算法概述 排序算法有许...

  • 常见排序算法

    这里介绍四种排序算法,选择排序、快速排序、归并排序、计数排序 选择排序(使用递归) 选择排序(使用循环) 快速排序...

  • 常用的两种排序-冒泡、选择

    Swift版 冒泡排序 选择排序 OC版 冒泡排序 选择排序

  • 数据结构之排序

    选择排序1.直接选择排序 原理直接选择排序过程直接选择排序过程 实现: DataWrap.java来模拟待排序的数...

  • 记录几个常见的排序算法

    常见的排序有:快速排序、冒泡排序、希尔排序、选择排序、插入排序、归并排序 冒泡排序: 插入排序: 选择排序: 希尔...

  • PHP常用算法

    基于选择的排序算法 常见的基于选择的排序算法有:冒泡排序、插入排序、选择排序、归并排序和快速排序,我们在选在排序算...

  • 排序 -- 选择/插入

    聊聊排序吧 冒泡排序 选择排序 插入排序 快速排序 归并排序 计数排序 桶排序 堆排序 本篇 选择排序与插入排序 ...

  • java快速学习排序---选择排序

    1.java实现选择排序 (1)、图解选择排序 (2)、选择排序的思想 选择排序首先在未排序序列中找到最小(大)元...

  • IOS 常用算法

    一:排序算法 排序方式有插入排序,选择排序和交换排序三种。插入排序有直接插入排序和希尔排序。选择排序有简单选择排序...

  • 给自己备份的排序代码

    交换排序 冒泡排序 快速排序 插入排序 直接插入排序 希尔排序 选择排序 简单选择排序 堆排序

网友评论

      本文标题:选择排序

      本文链接:https://www.haomeiwen.com/subject/hmasbktx.html