专栏首页python-爬虫常用的排序算法

常用的排序算法

常用的排序算法

li=[1,3,45,6,78,9,4]来举例

一.冒泡排序

空间复杂度O(n的2次方)

原理:例如你把一组数据从头开始依次遍历过去把最大的或者最小的放在末尾,除了最后一个每个依次进行遍历

def bubble_sort(li):
    for i in range(len(li)-1):
        flag = True
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                flag = False
        if flag:
            return
bubble_sort(li)

二.选择排序

空间复杂度O(n的2次方)

速度比冒泡快一点

原理:例如你把一篮子苹果让你从大到小进行排序,你就算先拿出一个,再拿出第二个和第一个比按大小摆放左还是右,再拿第三个和之前已经拍好顺序的队列进行对比放置合适位置,依次进行

def select_sort(li):
    for i in range(len(li)):
        minLoc = i
        for j in range(i+1, len(li)):
            if li[minLoc] > li[j]:
                li[minLoc], li[j] = li[j], li[minLoc]
select_sort(li)

三. 插入排序

空间复杂度O(n的2次方)

速度比选择快一点

原理:例如打牌手牌先抽出,再所有排进行排序,依次抽出依次进行排序替换

def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1
        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j]
            j = j - 1
        li[j+1] = tmp
insert_sort(li)

四.快速排序

时间复杂度:O(nlogn)

原理:有点类似二叉树取出一个值以他为基准大的放右边,小的放左边,然后依次递归下去

#递归调用的函数
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right = right - 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left = left + 1
        data[right] = data[left]
    data[left] = tmp
    return left

#递归函数
def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort(data, left, mid)
        quick_sort(data, mid + 1, right)

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • html基础总结

    multiple : 布尔属性,设置后允许多选,否则只能选择一个 disabled : 禁用该下拉列表 selected : 首次显示时,为选中状态 va...

    小小咸鱼YwY
  • Vue成员获取

    小小咸鱼YwY
  • 力扣题目汇总(最长特殊序列,回文数,移动零)

    小小咸鱼YwY
  • 谈谈一些有趣的CSS题目(七)-- 消失的边界线问题

    Sb_Coco
  • day 4 - 2 数据类型练习

    li = ['alex','wusir','eric','rain','alex']

    py3study
  • python基础知识练习题(二)

    2、利用下划线将列表的每一个元素拼接成字符串,li = ['alex','eric','Witharush']

    py3study
  • jquery入门

    周小董
  • 负margin在页面布局中的应用

    在页面中经常会遇到两列的情况,比如说左侧栏固定宽度,右侧栏自适应宽度,此时可以用flex布局的方式,但是这种方式在ie8上不兼容,但是也可以用table。这里我...

    无邪Z
  • 纯CSS编写三级导航菜单-附源码

    在我们日常浏览网站过程中,会发现每一个网站都会有导航栏,导航栏是做什么的?在一个网站中具有怎么样的意义呢?我们先来了解一下这个问题。

    申霖
  • python练习题-day12

    (3) 求M中3,6,9组成的列表M = [[1,2,3],[4,5,6],[7,8,9]]

    郭耀华

扫码关注云+社区

领取腾讯云代金券