Python学习(三) 八大排序算法的实现(上)

   本文Python实现了直接插入排序、基数排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、希尔排序。    上篇来介绍前四种排序方式:    下篇:八大排序算法的实现(下)

1、直接插入排序

描述    插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,       假设有一组无序序列 R0, R1, … , RN-1。 (1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。 (2) 然后,我们要依次把 R1, R2, … , RN-1 插入到这个有序序列中。所以,我们需要一个外部循环,从下标 1 扫描到 N-1 。 (3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述,我们可知,插入Ri时,前 i-1 个数肯定已经是有序了。 所以我们需要将Ri 和R0 ~ Ri-1 进行比较,确定要插入的合适位置。这就需要一个内部循环,我们一般是从后往前比较,即从下标 i-1 开始向 0 进行扫描。 分析 平均时间复杂度:O(n^2) 空间复杂度:O(1) 稳定性:稳定 代码实现

def insert_sort(lists):
    # 插入排序
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

2、基数排序

描述 基数排序(以整形为例),将整形10进制按每位拆分,然后从低位到高位依次比较各个位。主要分为两个过程: (1)分配,先从个位开始,根据位值(0-9)分别放到0~9号桶中(比如53,个位为3,则放入3号桶中) (2)收集,再将放置在0~9号桶中的数据按顺序放到数组中 重复(1)(2)过程,从个位到最高位(比如32位无符号整形最大数4294967296,最高位10位) 分析 平均时间复杂度:O(dn)(d即表示整形的最高位数) 空间复杂度:O(10n) (10表示0~9,用于存储临时的序列) 稳定性:稳定 代码实现

# encoding:utf-8
import math
def radix_sort(lists, radix=10):
    # lists为整数列表,radix为基数
    k = int(math.ceil(math.log(max(lists), radix)))
    # math.ceil函数是对浮点数向上取整,math.log函数是返回自然对数
    # 用K位数可以表示任意整数
    bucket = [[] for i in range(radix)]
    # K次循环
    for i in range(1, k+1):
        for j in lists:
            bucket[j/(radix**(i-1)) % (radix**i)].append(j)
        del lists[:]
        # del用于删除list中的一个或几个元素
        for each in bucket:
            lists.extend(each) # 桶合并
        bucket = [[] for i in range(radix)]
    return lists
#  基数排序的实现
def radix_sort(lists):
    bucket = [[] for _ in xrange(10)]    #首先得到十个桶
    for i in range(10):
        for j in lists:   #第一步入桶操作,将lists中的数分别入桶
            bucket[j/(10**i) % 10].append(j)
        del lists[:]       
        for k in bucket: #第二步出桶操作
            lists += k
            del k[:]     #一定要注意这两个del的缩进问题
    return lists        
print radix_sort(lists)

3.冒泡排序

描述 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。 分析 平均时间复杂度:O(n2) 空间复杂度:O(1) 稳定性:稳定

代码实现

#冒泡排序的实现
def bubble_sort(lists):
    count = len(lists)     #得到数组的长度,来判断接下来需要迭代的次数
    for i in xrange(0,count):
        for j in xrange(i+1,count):
            if lists[i] > lists[j]:
                lists[i],lists[j] = lists[j],lists[i]
            else:
                lists[i],lists[j] = lists[i],lists[j]
    return lists
print bubble_sort(lists)

4.快速排序

描述 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列 分析 平均时间复杂度:O(nlog2n) 空间复杂度:O(nlog2n) 稳定性:不稳定 代码实现

def quick_sort(lists, left, right):
    # 快速排序
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

C++指针类型识别正确姿势

  指针是C和C++中编程最复杂也是最有技巧的部分,但对于新手来说,指针无疑是最致命的,让很多人望而退步。不过很多事情都是从陌生开始,然后渐渐熟悉起来的,就像交...

1787
来自专栏积累沉淀

Java设计模式(五)----原型模式

原型模式(Prototype) 一、概述 二、结构 三、浅度克隆和深度克隆  浅度克隆  深度克隆 一、概述  定义:原型模式属...

1929
来自专栏木可大大

面向对象的演进过程

我们知道 程序 = 数据结构 + 算法,其中数据结构包括数组、栈、队列、链表、树以及图等,而算法是包含顺序、循环、分支三种逻辑结构的代码,为了使算法能够到处复用...

4279
来自专栏来自地球男人的部落格

[LeetCode] 152. Maximum Product Subarray

【原题】 Find the contiguous subarray within an array (containing at least one nu...

2025
来自专栏深度学习计算机视觉

计算A+B

代码很冗余 时间限制:1秒空间限制:32768K热度指数:347 **算法知识视频讲解 题目描述 给定两个整数A和B,其表示形式是:从个位开始,每三位数用...

2787
来自专栏desperate633

[编程题] 奇怪的表达式求值代码

常规的表达式求值,我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单,从左往右依次计算即可,而且小易所在的世界没...

621
来自专栏Java与Android技术栈

借助Java 8实现柯里化借助Java 8实现柯里化柯里化的好处总结

在函数式编程中,函数的概念跟数学中函数的概念是一样的,类似于“映射”。高阶函数和柯里化是函数式编程的特性。

922
来自专栏老九学堂

Java微课堂-运算符

Java运算符微视频笔记 赋值运算符 这讲的知识点不多,重点是大家要理解运算符的作用,运算符往往是和变量结合使用,用来解决一些常用的逻辑。比如赋值运算符就是给变...

3487
来自专栏人工智能LeadAI

为什么算法容易忘记之插入排序

在学习常用的排序算法时,常有这样的感觉,一看就懂,过眼就忘。原因在于没有将排序的基本思想与代码中各个循环控制变量的意义联系起来进行理解记忆。 插入排序 首先,我...

3485
来自专栏Linux Python 加油站

Python基础之set应用详解

一个{ }里面放一些元素就构成了一个集合,set里面可以是多种数据类型(但不能是列表,集合,字典,可以是元组)

1685

扫码关注云+社区