用Python实现十大经典排序算法

用Python实现十大经典排序算法

1.冒泡排序

冒泡排序（Bubble Sort）是一种比较简单的排序算法，它重复地走访过要排序的元素，依次比较相邻两个元素，如果它们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。

算法过程

比较相邻的元素，如果前一个比后一个大，就把它们两个对调位置。
对排序数组中每一对相邻元素做同样的工作，直到全部完成，此时最后的元素将会是本轮排序中最大的数。
对剩下的元素继续重复以上的步骤，直到没有任何一个元素需要比较。
冒泡排序每次找出一个最大的元素，因此需要遍历 n-1 次 （n为数据序列的长度）。

2.选择排序

选择排序（Selection Sort）的原理，每一轮从待排序的记录中选出最小的元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，然后放到已排序的序列的末尾。
以此类推，直到全部待排序的数据元素的个数为零。得到数值从小到达排序的数据序列。

也可以每一轮找出数值最大的元素，这样的话，排序完毕后的数组最终是从大到小排列。

选择排序每次选出最小（最大）的元素，因此需要遍历 n-1 次。

3.快速排序

先从数据序列中取出一个数作为基准数（baseline，习惯取第一个数）。
分区过程，将比基准数小的数全放到它的左边,大于或等于它的数全放到它的右边。
再对左右区间递归(recursive)重复第二步，直到各区间只有一个数。
因为数据序列之间的顺序都是固定的。最后将这些子序列一次组合起来，整体的排序就完成了。

4 归并排序

主要两步(拆分，合并)

步骤１：进行序列拆分，一直拆分到只有一个元素；
步骤２：拆分完成后，开始递归合并。
思路：假设我们有一个没有排好序的序列，那么我们首先使用拆分的方法将这个序列分割成一个个已经排好序的子序列（直到剩下一个元素）。然后再利用归并方法将一个个有序的子序列合并成排好序的序列。

5 堆排序

对于 n 个元素的数据序列 ，当且仅当满足下列情形之一时，才称之为 堆:

6 插入排序

插入排序(Insertion Sort)就是每一步都将一个需要排序的数据按其大小插入到已经排序的数据序列中的适当位置，直到全部插入完毕。

插入排序如同打扑克牌一样，每次将后面的牌插到前面已经排好序的牌中。

7 希尔排序

希尔排序(Shell Sort)是插入排序的一种更高效率的实现。

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。

8 计数排序

计数排序（Counting Sort）的核心在于将输入的数据值转化为键，存储在额外开辟的数组空间中。计数排序要求输入的数据必须是有确定范围的整数。

算法的步骤如下：

先找出待排序的数组中最大和最小的元素，新开辟一个长度为 最大值-最小值+1 的数组
然后，统计原数组中每个元素出现的次数，存入到新开辟的数组中；
接下来，根据每个元素出现的次数，按照新开辟数组中从小到大的秩序，依次填充到原来待排序的数组中，完成排序。

9 桶排序

简单来说，桶排序（Bucket Sort）就是把数据分组，放在一个个的桶中，对每个桶里面的数据进行排序，然后将桶进行数据合并，完成桶排序。

该算法分为四步，包括划分桶、数据入桶、桶内排序、数据合并。

10 基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），它是透过键值的部份信息，将要排序的元素分配至某些“桶”中，以达到排序的作用。

基数排序适用于所有元素均为正整数的数组。