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

相关文章

来自专栏Android机器圈

递归 —— 二分查找法 —— 归并排序

二分法就是把一个数组折半查找,再折半直到找到数据位置,或者无数据位置。比如说1-100,你选的值是23,那么范围写法就是(索引写法类似)

1224
来自专栏专注研发

桶排序/基数排序(Radix Sort)

基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要...

792
来自专栏Golang语言社区

Go语言实现冒泡和快速排序

冒泡和快速排序都属于交换类排序,所谓交换排序是指借助数据元素之间互相交换进行排序的方法。 冒泡排序法 冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据的...

3176
来自专栏Android机器圈

排序算法

上面结果可以说明,虽然也是比较了和冒泡一样多的次数,但是交换缺少了很多。所以时间为N²/2

1745
来自专栏老秦求学

快速排序

快速排序: 设要排序的数组是A[0]……A[N-1], 思想:分治法(递归实现)关键是求出基准记录所在的位置(由于两个数之间进行交换,导致原来基准的位置发生改变...

2696
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

510
来自专栏和蔼的张星的图像处理专栏

433. 岛屿的个数遍历加递归

给一个01矩阵,求不同的岛屿的个数。 0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

521
来自专栏用户2442861的专栏

桶排序

http://blog.csdn.net/houapple/article/details/6480100

884
来自专栏Golang语言社区

Go语言实现冒泡和快速排序

冒泡和快速排序都属于交换类排序,所谓交换排序是指借助数据元素之间互相交换进行排序的方法。 冒泡排序法 冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据的...

3337
来自专栏Android机器圈

算法:插入排序详解--为什么从第二项开始,而不是第一项

PS:对于插入排序这个算法,我们想要看清他就要从它的应用场景,概念,用法等去了解它,实现代码就那么几行,但有时还真是不好理解,比如说为什么从第二项开始,而不是从...

3726

扫码关注云+社区