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 条评论
登录 后参与评论

相关文章

来自专栏恰同学骚年

数据结构基础温故-4.树与二叉树(上)

前面所讨论的线性表元素之间都是一对一的关系,今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用,甚至在计算机的日常使用中,也可以看到树形...

803
来自专栏王硕

原 B树C语言代码实现

4799
来自专栏LeetCode

LeetCode 114. Flatten Binary Tree to Linked List

关于二叉树的题目,最直接最简单的方法就是采用递归,因为二叉树具有天然的递归结构,实际上二叉树的定义就是用递归的思想来定义的:一个节点的左右子树任然是一个二叉树。

150
来自专栏Coding迪斯尼

在未知长度的超大数组中线性时间内查找第k大的元素

给定一个长度为n的数组,n是一个很大的值,而且事先不知道n的大小,给定一个确定的数值k,要求设计一个找出数组中第k大的元素,要求算法需要的空间不能超过O(k)。

872
来自专栏青玉伏案

算法与数据结构(十) 二叉排序树的查找、插入与删除(Swift版)

在上一篇博客中,我们主要介绍了四种查找的方法,包括顺序查找、折半查找、插入查找以及Fibonacci查找。上面这几种查找方式都是基于线性表的查找方式,今天博客中...

1917
来自专栏书山有路勤为径

移除K个数字

LeetCode 402. Remove K Digits 已知一个使用字符串表示的非负整数num,将num中的k个数字移除, 求移除k个数字后,可以获得的...

823
来自专栏大闲人柴毛毛

贪心算法(四)——最小代价生成树

问题描述 n个村庄间架设通信线路,每个村庄间的距离不同,如何架设最节省开销? 这个问题中,村庄可以抽象成节点,村庄之间的距离抽象成带权值的边,要求最节约...

4516
来自专栏LeetCode

LeetCode <Stack>84&85. Maximal Rectangle&Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the ...

1185
来自专栏King_3的技术专栏

leetcode-36-有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

632
来自专栏小樱的经验随笔

Vijos P1114 FBI树【DFS模拟,二叉树入门】

描述 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树1,它的...

2639

扫码关注云+社区