Python小知识 - 八大排序算法

八大排序算法

排序算法是计算机科学中非常重要的一个研究领域。排序算法可以分为内部排序和外部排序，内部排序是数据记录在计算机内部，而外部排序是数据记录在计算机外部，这里我们主要讨论内部排序。

内部排序中的算法大致可以归纳为四类：插入排序、选择排序、交换排序和归并排序。其中插入排序包括直接插入排序和折半插入排序；交换排序包括冒泡排序和快速排序；归并排序又分为两种：二路归并排序和多路归并排序。

直接插入排序

直接插入排序（straight insertion sorting）的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。该方法又称简单插入排序。

直接插入排序是稳定的排序方法。

直接插入排序的时间复杂度是：

T(n) = O(n2)

下面我们用Python来实现直接插入排序。

首先定义一个函数insert_sort()，该函数的参数是一个列表，我们将列表中的数据按照直接插入排序的方法进行排序，并将排序后的结果返回。

```python def insert_sort(lst): 遍历列表中的所有元素 for i in range(1, len(lst)): 从第二个元素开始，将其与前一个元素比较，如果小于前一个元素，则将其与前一个元素交换位置 for

顺便介绍一下我的另一篇专栏， 《100天精通Python - 快速入门到黑科技》专栏，是由 CSDN 内容合伙人丨全站排名 Top 4 的硬核博主 不吃西红柿 倾力打造。 基础知识篇以理论知识为主，旨在帮助没有语言基础的小伙伴，学习我整理成体系的精华知识，快速入门构建起知识框架；黑科技应用篇以实战为主，包括办公效率小工具、爬虫、数据分析、机器学习、计算机视觉、自然语言处理、数据可视化等等，让你会用一段简单的Python程序，自动化解决工作和生活中的问题，甚至成为红客。

🍅 订阅福利：原价299，限时1折订阅专栏进入千人全栈VIP答疑群，作者优先解答机会（代码指导/学习方法指引），群里大佬可以抱团取暖（大厂/外企内推机会）

🍅 订阅福利：简历指导、招聘内推、80G全栈学习视频、300本IT电子书：Python、Java、前端、大数据、数据库、算法、爬虫、数据分析、机器学习、面试题库等等

🍅 专栏地址： 点击《100天精通Python - 快速入门到黑科技》