文档章节

python--8大排序(原理+代码)

o
 osc_e3fen7cx
发布于 2019/07/19 14:20
字数 1077
阅读 22
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

常用的排序方法:冒泡排序、选择排序、插入排序、快速排序、堆排序、归并排序

 

冒泡排序(Bubble Sort):

  比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
  对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  针对所有的元素重复以上的步骤,除了最后一个。
  持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较

def bubble_sort(alist):
    n = len(alist)
    for i in range(n-1):   
        for j in range(n-1-i):
            if alist[j] > alist[j+1]:
                alist[j],alist[j+1] = alist[j+1],alist[j]
if __name__ == '__main__':
    alist = [1,2,4,9,5,6,8]
    bubble_sort(alist)
    print(alist)

最优时间复杂度:O(n)
最坏时间复杂度:O(n2)

空间复杂度:o(1)
稳定性:稳定

  

 

选择排序(Selection sort):

  首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
  然后,再从剩余未排序元素中继续寻找最小(大)元素,
  然后放到已排序序列的末尾。
  以此类推,直到所有元素均排序完毕。

def select_sort(alist):
    n = len(alist)
    for i in range(n-1):
        min_index = i
        for j in range(i+1,n): # 遍历无序序列
            # 判断当前数值是否小于最小值,如果小于,则记录其索引
            if alist[j] < alist[min_index]:
                min_index = j
        # 判断min_index索引是否相同,不相同,做数值交换
        if i != min_index:
            alist[i],alist[min_index] = alist[min_index],alist[i]
if __name__ == '__main__':
    alist = [12,34,56,78,90,87,65,43,21]
    select_sort(alist)
    print(alist)

最优时间复杂度:O(n*log2n)
最坏时间复杂度:O(n2)

空间复杂度:O(log2n)~o(n)
稳定性:不稳定

 

 

插入排序:

    开始假定列表里下标为0的元素是最小,在后面还未排序的数据里依次选取数据在前面有序区域里做比较并放在正确的位置,就像我们在玩扑克牌的时候依次把扑克牌有顺序的拜访

import random
def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]     #tmp是无序区取出的一个数
        j = i - 1       #li[j]是有序区最大的那个数
        while j >= 0 and li[j] > tmp:
         # li[j]是有序区最大的数,tmp是无序区取出的一个数,tmp从有序区最大的那个数开始比
         # 小就调换位置,直到找到有序区中值不大于tmp的结束
            li[j+1]=li[j]    #将有序区最右边的数向右移一个位置
            j = j - 1
        li[j + 1] = tmp       #将tmp放到以前有序区最大数的位置,再依次与前一个数比较
data = list(range(100))
random.shuffle(data)        #将有序列表打乱
insert_sort(data)
print(data)
时间复杂度:o(n2)
空间复杂度:o(1)
稳定性:稳定

 

 

快速排序:

  随机选取一个值,挨个跟后面的数值作比较,比该数值小的将放在左列表中,反之则放在右列表,返回形式为:左列表+[随机值]+右列表,左右列表使用递归的方式继续进行排序。

def quick(list):
    if len(list) < 2:
        return list
    tmp = list[0]  # 临时变量 可以取随机值
    left = [x for x in list[1:] if x <= tmp]  # 左列表
    right = [x for x in list[1:] if x > tmp]  # 右列表
    return quick(left) + [tmp] + quick(right)

li = [4,3,7,5,8,2]
print(quick(li))

时间复杂度:O(nlog₂n)
空间复杂度:O(nlog₂n)
稳定性:不稳定

 

 

堆排:

  堆总是一棵完全二叉树,构造堆、调整堆

  构造堆:每个根节点总是大于等于其子节点,从最小堆依次往上做调整

  调整堆:将堆顶最大元素出堆,将最后一个元素放至堆顶,然后用构造堆的方法进行调整,此过程循环往复,将数据从大到小的顺序依次出堆,直至此堆变空。

   时间复杂度:O(nlogn)

  空间复杂度:O(1)

  稳定性:不稳定

 

归并排序:

  将列表越分越小,直至分成一个元素,一个元素是有效的,然后将两个有序的列表合并。

  时间复杂度:O(nlog₂n)

  空间复杂度:O(1)

  稳定性:稳定

 

整理自:https://www.cnblogs.com/xiaonq/p/8573587.html

 

 

 

  

  

  

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Swift百万线程攻破单例(Singleton)模式

一、不安全的单例实现 在上一篇文章我们给出了单例的设计模式,直接给出了线程安全的实现方法。单例的实现有多种方法,如下面: class SwiftSingleton { } 这段代码的实现,在shared中进行条...

一叶博客
2014/06/20
3.3K
16
Nutch学习笔记4-Nutch 1.7 的 索引篇 ElasticSearch

上一篇讲解了爬取和分析的流程,很重要的收获就是: 解析过程中,会根据页面的ContentType获得一系列的注册解析器, 依次调用每个解析器,当其中一个解析成功后就返回,否则继续执行下一个解...

强子哥哥
2014/06/26
712
0
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
数据库代码辅助工具--MaoCaiJun.Database

MaoCaiJun.DataBase 是一个用于 Microsoft Visual Studio 的数据库代码生成组件。它是基于 xml 文件的代码创建工具,支持sql2000,sql2005,sql2008,access, SQLite MaoCaiJun.Database 数据库...

mccj
2013/02/06
2.3K
1
C/C++ 代码文档生成器--cldoc

cldoc 是一个使用 clang 实现的 C/C++ 代码文档生成器。 特点: 使用 clang 可靠解析大多数复杂的 C++ 项目 零配置 使用 markdown 做为文档格式 生成描述 API 的 XML 文档 使用简单格式用于文...

匿名
2013/02/14
1.4K
0

没有更多内容

加载失败,请刷新页面

加载更多

什么是移动语义? - What is move semantics?

问题: I just finished listening to the Software Engineering radio podcast interview with Scott Meyers regarding C++0x . 我刚刚结束了对Scott Meyers进行的有关C ++ 0x的Software En......

技术盛宴
52分钟前
24
0
算法与数据结构体系课

算法与数据结构体系课【超清原画】 下载地址:百度云盘 从0到工作5年,面试、进大厂、搭建知识体系、拓展技术上限 你不再需要其它算法与数据结构课程了 为什么学算法已经是一个不应该问的问题...

1930133570
今天
21
0
如何停止跟踪并忽略对Git中文件的更改? - How to stop tracking and ignore changes to a file in Git?

问题: I have cloned a project that includes some .csproj files. 我已经克隆了一个包含一些.csproj文件的项目。 I don't need/like my local csproj files being tracked by Git (or bei......

富含淀粉
今天
25
0
Redis阻塞

可能存在问题 内在原因:API或数据结构使用不合理、CPU饱和、持久化阻塞等 外在原因:CPU竞争、内存交换、网络问题等 问题处理: API或数据结构使用不合理,可能存在慢查询或者大对象: 发现...

游泳鸟
今天
17
0
OSChina 周五乱弹 —— 来人,上幼儿园老师跳舞的图!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑:《奇跡の海》- 坂本真綾 《奇跡の海》- 坂本真綾 手机党少年们想听歌,请使劲儿戳(这里) 巴蜀(@巴拉迪维)最近有点闹心了, @巴...

小小编辑
今天
64
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部