GitHub星数13200!用Python实现所有排序算法的开源项目你见过么?

综合自:GitHub详情页

本月榜单有一个项目成功吸引了我的注意,该项目用Python实现了所有的排序算法,包括插入排序、冒泡排序、快速排序、选择排序、归并排序等。

截至今日,该项目已经获得了13200个「star」以及3758个「fork」(GitHub项目地址:https://github.com/TheAlgorithms/Python)

该创建者表示这些仅用于演示学习。由于性能的原因,Python标准库中有许多排序实现。

1、冒泡排序

冒泡排序,有时也称为下沉排序,是一种简单的排序算法,它反复遍历要排序的列表,一次比较两个元素,如果它们的顺序错误则交换它们。重复遍历列表,直到不再需要交换,说明该列表排序完成。

性能分析

● 冒泡排序在最坏的情况下的比较次数是O(N^2)

● 冒泡排序在最坏的情况下的比较次数是O(N)

代码实现

2、插入排序

插入排序是一种简单的排序算法,可以一次构建一个项目的最终排序数组(或列表)。它在大型列表上的效率远低于更高级的算法,如快速排序,对堆排序或归并排序。

代码实现

3、归并排序

归并排序(MERGE-SORT)是一种有效的、通用的,基于比较的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。由John von Neumann于1945年发明。

属性

● 最好时间复杂度O(nlogn)

● 最坏时间复杂度O(nlogn)

● 平均时间复杂度O(nlogn)

代码实现

归并排序在多种情况下都是首选的算法:当需要稳定性时,当排序链表时,当随机访问比顺序访问复杂得多时(例如,磁带上的外部排序)。

4、快速排序

快速排序(也被称为分区交换排序)是一种有效的排序算法,用作按顺序放置数组元素的系统方法。

代码实现

5、选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

代码实现

选择排序的特性是最小化交换的数量。在交换项成本很高的应用程序中,选择排序可能是一种很好的选择算法。

6、希尔排序

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因D.L.Shell于1959年提出而得名。

属性

● 最好时间复杂度O(nlog2 2n)

● 最坏时间复杂度O(n log n)

● 平均时间复杂度表现取决于差距序列

实现代码

●编号416,输入编号直达本文

●输入m获取文章目录

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181011B0LP3800?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券