用Python实现十大经典排序算法-插入、选择、快速、冒泡、归并等

本文来用图文的方式详细讲解了Python十大经典排序算法 —— 插入排序、选择排序、快速排序、冒泡排序、归并排序、希尔排序、插入排序、桶排序、基数排序、计数排序算法，想要学习的你们，继续阅读下去吧，如果觉得不错的话，推荐给身边的朋友吧。

插入排序

思路

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置；
重复步骤2~5。

代码

图示

平均时间复杂度

O(n^2)

希尔排序

前言

希尔排序是插排的升级，先将待排序的元素进行分组，在分组的基础上进行插排，从而降低整体上的时间复杂度。

这里面设计到一个增量的概念，我们依据增量来决定分组的跨度。常用的增量有三种：

希尔增量 [1,2,4,8,…,2^(k-1)]
海巴德增量 [1,3,7,15,…,2^k-1]
塞基维克增量 [1,5,19,41,…,4k-3*2k+1]

一般情况下希尔增量带来的时间复杂度小于O(n2),但在极坏情况下可能效果不明显甚至超过这个值。海巴德增量可以将时间复杂控制在O(n(3/2))以下，而塞基维克增量该项参数为O(n^(4/3))。

思路

择定增量
分组
组内比较
重复步骤2,3直到跨度为1

图示

代码

选择排序

思路

选出数组中最大（最小）的元素放到开头
在剩下的元素中选中最大（最小）元素放到上个被选元素之后
重复2步骤

图示

代码

平均时间复杂度

O(n^2)

堆排序

前言

堆排序，顾名思义，就是基于堆。因此先来介绍一下堆的概念。

堆分为最大堆和最小堆，其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子，最小堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求，其实很好理解。有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。