05-选择排序

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_43908900/article/details/102556912

选择排序算法的原理:

选择排序是从冒泡排序演化而来的,每一轮(趟)比较出最小的那个值,放到第一个位置,然后在每轮的无序区中选出最小的值放到第二个位置。

目的:从小到大排序

图示:

算法的关键点是:有序区跟无序区、无序区最小的位置

首先我们写一个简单的选择排序,用到python的内置模块:

#思路是我们创建一个新列表,将原列表中的最小数选出后添加到新列表的中,实现排序。
#定义一个简单的选择排序
def select_sort_simple(li):
    list_new = []
    for i in range(len(li)):
        min_num = min(li)
        list_new.append(min_num)
        li.remove(min_num)
    return list_new

li = [2,5,1,7,4,9,3,0]
print(select_sort_simple(li))

结果:[0, 1, 2, 3, 4, 5, 7, 9]

缺点:

  • 我们生成了一个新的列表,原来需要1G内存的列表,现在需要2G内存,且复杂度增加
  • 里面使用的min\remove复杂度都不是O(1),而是O(n),(remove(O(n)):remove删除元素后,后面元素需要补齐)-----该程序的复杂度为O(n^2)

回归主线,使用代码解释选择排序算法,我们的需求是什么===》不产生新列表,并且每趟将原列表无序区中最小的数放在第一个位置、第二个位置…

换种说法就是先找出原列表的最小值然后与列表的第一个位置上的元素进行交换。

最多需要N趟,每趟出来一个数,但是N-1趟结束后,无序区只剩一个数不要走一边,所以我们最多需要N-1趟,每一趟都需要便利无序区,无序区的范围是:第0趟:从0到最后,第1趟:从1到最后,…所以无序区的范围:i+1 — len(i)。

我们还需要记录最小值的位置:min_loc = i(假定无序区的第一个位置为最小值)

#选择排序的优解
def select_sort(li):
    for i in range(len(li)-1):
        min_loc = i
        for j in range(i+1,len(li)):
            if li[j] < li[min_loc]: #无序区第一个数小于最小值
                min_loc = j #赋值
        li[min_loc],li[i] = li[i],li[min_loc] #两个数交换
        print(li)

li = [2,5,1,7,4,9,3,0]
print(li)
select_sort(li)

结果:

[2, 5, 1, 7, 4, 9, 3, 0]
[0, 5, 1, 7, 4, 9, 3, 2]
[0, 1, 5, 7, 4, 9, 3, 2]
[0, 1, 2, 7, 4, 9, 3, 5]
[0, 1, 2, 3, 4, 9, 7, 5]
[0, 1, 2, 3, 4, 9, 7, 5]
[0, 1, 2, 3, 4, 5, 7, 9]
[0, 1, 2, 3, 4, 5, 7, 9]

学习网站、分享及成功:http://www.xbhog.cn

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 04-冒泡排序实现

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    xbhog
  • ZOL桌面壁纸的提取

    这是爬虫的第一部分,对于python基础与网络编程部分重点突出,主要以每次小项目为主;更新时间不定,随缘之人,缘分到了,文章就出来了。

    xbhog
  • Django中的url与视图详解(2)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    xbhog
  • 你真的理解HTML5标签语义化吗?

    <head>标签用于定义文档的头部,它是所有头部元素的容器。<head>描述了文档的各种属性和信息,包括文档的标题、在 Web 中的位置以及和其他文档的关系等。...

    陈大鱼头
  • JS-制作网页特效——选项卡效果(水平,点击)

    xing.org1^
  • 3.列表-HTML基础

    到现在为止,我们学习了很多标签,但是由于不熟悉标签的语义化,有时我们可能会用别的标签代替另一个标签,从而实现相同的效果,但这是一种错误的思想。

    见贤思齊
  • 详解: :hover 12 三种方式 唉,累死我了看评论啊啊啊

    核心是:触碰到哪里,记住是触碰哈,因为not所以触碰的没有效果,其他的都有效果,问题什么效果? opacity: .2; filter: alpha(opa...

    用户7873631
  • 使用CSS制作文字环绕图片效果(文字内容包含<li>标签)

    1.一般制作文字环绕图片效果。 HTML结构: View Code <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1....

    八哥
  • Cypress学习12-父子元素定位

    若要在元素中获取所有下一个同级DOM元素,直到另一个元素,请使用.next until()命令。

    上海-悠悠
  • bootstrap 分页 常用样式 1

    pagination <ul class="pagination"> <li><a href="#">«</a></li> <li><a href...

    用户5760343

扫码关注云+社区

领取腾讯云代金券