Python基本的排序算法比较,sorted的实现方法

算法与数据结构基础

查找算法:

二分查找法:

简介:二分查找法又被称为折半查找法,用于预排序的查找问题

过程:

  1. 如果在列表a中查找元素t,先将列表a中间位置的项与查找关键字t比较,如果两者相等,则成功。
  2. 否则,将表分为前后两个子表
  3. 如果中间位置大于t,则进一步查找前一子表,否则,查找后一子表
  4. 重复上述过程

优劣:

  1. 时间复杂度为O(log2N),比较快
  2. 缺点就是必须是有序列表

排序算法:

冒泡排序

简介:两两比较大小,如果不满足升序关系,则交换

过程:略

优劣::

  1. 时间复杂度为O(N2),速度较慢
  2. 稳定

选择排序

简介:找出最小值,然后放入一个新的列表中

过程:略

优劣::

  1. 时间复杂度为O(N2),速度较慢
  2. 稳定

插入排序法

简介:依次检查需要排序的列表,每次取出一个元素放入另一个排好序的列表中的适当位置。

过程:略

优劣::

  1. 时间复杂度为O(N2)
  2. 速度不稳定,最佳情况为线性增长,最差情况为N2,所以速度实际上比前两种快

归并排序

简介:分而制之的思想

过程:

  1. 将包含N个元素的列表分为两个含N/2元素的子列表.
  2. 对两个子列表递归调用归并排序(最后将两个子列表分解为N个子列表)。
  3. 合并已排序好的列表。

劣::速度较快且稳定,时间复杂度为O(Nlog2N)

实现代码:

def merge(left,right):
    merged = []
    i,j = 0,0
    left_len,right_len = len(left),len(right)    while i<left_len and j<right_len:        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])        return mergeddef mergeSort(a):    if len(a) <= 1:        return a    else:        mid = len(a) // 2
        left = mergeSort(a[:mid])        right = mergeSort(a[mid:])        merge(left,right)        return merge(left,right)def main():
    a = [59,12,77,64,72,69,46,89,31,9]
    a1 = mergeSort(a)
    print(a1)if __name__ == '__main__':    main()

快速排序 #:

简介:对冒泡排序的改进

过程:

  1. 设置两个变量i和j,作为列表首末两端的下标,即i=0,j=N-1
  2. 设置列表的第一个元素作为关键数据,即key=A[0]
  3. 从j开始向前搜索,找到第一个小于key的值A[j],将A[j]和A[i]互换
  4. 从i开始向后搜索,找到第一个大于key的值A[i],将A[i]和A[j]互换
  5. 重复3~4步,直到i = j

优劣::

  1. 平均情况时间复杂度为O(Nlog2N),比较快。
  2. 最差情况下时间复杂度为O(N2)

Python语言中提供的排序算法

内置数据类型list的方法sort(),内置函数sorted()

这个的底层实现就是归并排序,只是使用了Python无法编写的底层实现,从而避免了Python本身附加的大量开销,速度比我们自己写的归并排序要快很多(10~20倍),所以说我们一般排序都尽量使用sorted和sort

原文发布于微信公众号 - Python雁横(py_0123)

原文发表时间:2018-07-19

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

动画+原理+代码,解读十大经典排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

16730
来自专栏目标检测和深度学习

排序算法算法对比

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

35760
来自专栏CodingBlock

Java数据结构和算法总结-字符串相关高频面试题算法

前言:周末闲来无事,在七月在线上看了看字符串相关算法的讲解视频,收货颇丰,跟着视频讲解简单做了一下笔记,方便以后翻阅复习同时也很乐意分享给大家。什么字符串在算...

41100
来自专栏落影的专栏

程序员进阶之算法练习(三十四)LeetCode专场

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

15240
来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:数组全解!!

正文之前 其实我的《C++ Primer》 已经看到第五章了,但是因为码字比较费时间,所以暂时没有迅速更新实在是对不住,但是没办法, 总不能一天拿出五六个小时来...

364100
来自专栏云霄雨霁

排序----希尔排序

16800
来自专栏人工智能LeadAI

排序算法对比、总结(Python代码)

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

41980
来自专栏彭湖湾的编程世界

【算法】希尔排序学习笔记

【参考资料】 《算法(第4版)》         — — Robert Sedgewick, Kevin Wayne 在本篇笔记里,我从简单的插入排序,到希尔排...

24580
来自专栏Java编程

四道Java基础题,你能对几道?

如果这道题你能得出正确答案,并能了解其中的原理的话。说明你基础还可以。如果你的答案 是 true 和true的话,你的基础就有所欠缺了。

1.1K10
来自专栏Crossin的编程教室

【Python 第72课】map 函数

来看两个问题: 1. 假设有一个数列,如何把其中每一个元素都翻倍? 2. 假设有两个数列,如何求和? 第一个问题,普通程序员大概会这么写: lst_1 = [...

323100

扫码关注云+社区

领取腾讯云代金券