python实现常见的五种排序算法

keelii 发布于2019-07-31 11:04 / 1965人阅读

摘要：概要算法理论讲解有专业的书籍和视频资源，本篇文章主要展示算法排序的语言描述，具体讲解的资源地址参见文末参考引用冒泡排序冒泡排序打印结果为选择排序选择排序打印结果为插入排序插入排序打印结果为归并排序归并排序分归并排序治打印结果为

概要

算法理论讲解有专业的书籍和视频资源，本篇文章主要展示算法排序的python语言描述，具体讲解的资源地址参见文末参考引用

冒泡排序(Bubble Sort)

# 冒泡排序
def bubbleSort(seq=None, reversed=False):
    lens = len(seq)
    for i in range(lens):
        for j in range(lens - i - 1):
            if (seq[j] < seq[j + 1] if reversed else   seq[i] > seq[j]):
                seq[j], seq[j + 1] = seq[j + 1], seq[j]
    return seq

if __name__=="__main__":
    #打印结果为：[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    print(bubbleSort([10, 1, 3, 5, 7, 9, 2, 4, 6, 8, 11, 15, 0, 12, 14, 13],True))

选择排序(Selection Sort)

# 选择排序
def selectionSort(seq=None, reversed=False):
    lens = len(seq)
    for i in range(lens):
        min_index = i
        for j in range(i + 1, lens):
            if (seq[min_index] < seq[j] if reversed else   seq[i] > seq[j]):
                min_index = j
        seq[i], seq[min_index] = seq[min_index], seq[i]
    
    return seq


if __name__ == "__main__":
    # 打印结果为：[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    print(selectionSort([10, 1, 3, 5, 7, 9, 2, 4, 6, 8, 11, 15, 0, 12, 14, 13], True))

插入排序(Insertion Sort)

# 插入排序
def insertionSort(seq=None, reversed=False):
    lens = len(seq)
    for i in range(1, lens):
        key = seq[i]
        j = i
        while j > 0 and (seq[j - 1] < seq[j] if reversed else    seq[j - 1] > seq[j]):
            seq[j], seq[j - 1] = seq[j - 1], seq[j]
            j -= 1
    
    return seq


if __name__ == "__main__":
    # 打印结果为：[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    print(insertionSort([10, 1, 3, 5, 7, 9, 2, 4, 6, 8, 11, 15, 0, 12, 14, 13], True))

归并排序(Selection Sort)

# 归并排序(分）
def mergeSort(seq):
    if len(seq) < 2:
        return seq
    mid = len(seq) // 2
    left = mergeSort(seq[:mid])
    right = mergeSort(seq[mid:])
    return merge(left, right)


# 归并排序（治）
def merge(left, right):
    if not len(left) or not len(right):
        return left or right
    result = []
    i, j = 0, 0
    
    while (len(result) < len(left) + len(right)):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break
    return result


if __name__ == "__main__":
    # 打印结果为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    print(mergeSort([10, 1, 3, 5, 7, 9, 2, 4, 6, 8, 11, 15, 0, 12, 14, 13]))

快速排序(Selection Sort)

# 快速排序
def quickSort(seq, start, end):
    if start < end:
        split = partition(seq, start, end)
        quickSort(seq, start, split - 1)
        quickSort(seq, split + 1, end)
    return seq


def partition(seq, start, end):
    pivot_index = start - 1
    for i in range(start, end):
        # 选择最右边的为pivot
        if seq[i] < seq[end]:
            pivot_index += 1
            seq[pivot_index], seq[i] = seq[i], seq[pivot_index]
    seq[end], seq[pivot_index + 1] = seq[pivot_index + 1], seq[end]
    return pivot_index + 1


if __name__ == "__main__":
    # 打印结果为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    print(quickSort([10, 1, 3, 5, 7, 9, 2, 4, 6, 8, 11, 15, 0, 12, 14, 13], 0, 15))

参考引用

1, sole learn，ios、android均可免费下载
2, github源文件地址
3，北大公开课算法设计与分析屈婉玲教授
4，数据结构-浙江大学
5，算法(普林斯顿大学)

GPU云服务器云服务器下的五种负载均衡的五种策略常见机器学习算法机器学习常见算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44578.html

一个两年Java的面试总结

摘要：数据结构和算法树快速排序，堆排序，插入排序其实八大排序算法都应该了解一致性算法，一致性算法的应用的内存结构。如何存储一个的。八大排序算法一定要手敲一遍快排，堆排尤其重要。面试是一个双向选择的过程，不要抱着畏惧的心态去面试，不利于自己的发挥。前言 16年毕业到现在也近两年了，最近面试了阿里集团（菜鸟网络，蚂蚁金服），网易，滴滴，点我达，最终收到点我达，网易offer，蚂蚁金服二面挂掉，...

anRui 2019-08-15 14:34 评论0 收藏0
五种最大公约数Python求解总结

　　小编写这篇文章的主要目的，主要是给大家讲解一下，关于最大公约数的求解方法，下面小编集中给大家总结一下，具体操作的五种方法。　　方法一：短除法　　短除法是求最大公因数的一种方法，也可用来求最小公倍数。求几个数最大公因数的方法，开始时用观察比较的方法，即：先把每个数的因数找出来，然后再找出公因数，最后在公因数中找出最大公因数。后来，使用分解质因数法来分别分解两个数的因数，再进行运算。之后又演变为短...

89542767 2022-10-10 16:14 评论0 收藏0
this的五种指法

摘要：中只有的作用域是动态作用域的五种绑定初学时，会想当然认为遵循某一条规律，就像物理学那样，然而并不是。的绑定分为五种情况，这五种情况之间毫无规律可言。以至指向更加扑朔迷离。 this 到底指向哪里以下如果没提及，则为严格模式。 js中作用域有两种: 词法作用域动态作用域词法作用域词法作用域指在书写代码时就被确定的作用域。看如下代码 var value = 1; ...

Caizhenhao 2019-08-23 14:26 评论0 收藏0
未来五年内将重塑大数据技术的五种趋势

摘要：所谓大数据及其相关技术在经历了高度重视详细甄别以及吐故纳新之后，实际成果很可能与我们的认知存在较大差异。他们将探讨与大数据相关的各类话题，内容涵盖对抗贩卖人口未来发展方向乃至人工智能前沿技术。请大家不要再纠结于一块磁盘能保存多少数据或者企业到底会不会采用Hadoop。关于大数据的真正问题在于，企业用户将如何使用Hadoop、我们的系统到底能在智能化道路上走多远、我们又该如何保证这一切都处于...

learn_shifeng 2019-04-25 17:36 评论0 收藏0