python排序算法

一、冒泡排序

一种简单的排序方法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换。

走访数列的工作是重复地进行直到不需要进行交换，也就是说该数列已经排序完成。这个算法的名字由来是因为元素会慢慢“浮”到数列的顶端。

1.比较相邻的元素。如果该元素比后一个元素大，就进行交换

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该是最大的数

3.针对所有元素重复上述步骤，除了最后一个

4.重复1-3，直到排序完成

注：其实每一次循环都会有一个数排到对的位置，随着循环次数的增加，步骤3可以不用对所有的元素重复

二、选择排序

选择排序和冒泡类似，可以看作是对冒泡排序的优化。

1.找到数组中最大的那个元素

2.将它和数组中第一个元素进行交换，如果第一个元素就是最大的元素就和自己交换

3.在剩下的元素中找到最大的元素，将它和第二个元素进行交换。如此反复，直到将整个数组排序。

4.这种方法叫做选择排序是因为它在不断的选择剩余元素中的最大者

注：最大可以改为最小

三、插入排序

像打麻将一样，把摸到的麻将插入到合适的位置，适合近乎有序的数组。

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素都向后移动一位。

插入排序所需的时间取决于输入元素的初始顺序，例如：对一个很大且元素已经近乎有序的数组经行排序会比随机顺序的数组或是逆序数组进行排序要快得多。

注：插入排序对于部分有序的数组十分高效，也适合小规模数组。

四、快速排序

快速排序是对冒泡排序的一种改进，也是采用分治法的典型应用。

首先任意选取一个数据作为关键数据，我们称为基准数。

然后将所有比它小的数都放到它的前面，所有比它大的数都放到它的后面，

这个过程称为一趟快速排序，也称分区操作。

通过一趟快速排序要将排序的数据分割成独立的两部分，

其中一部分数据都比另一部分所有数据要小。

然后再按此方法对两部分数据分别进行快速排序，

整个排序过程可以递归进行，以此将整个数据变成有序数据。

五、希尔排序

这是一种基于插入排序的快速排序算法。简单插入对于大规模乱序数组很慢，因为元素只能一点一点地从数组的一端移动到另一端。

希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法是冲破第一批算法之一。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法；然后缩小增量继续分组，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分为一组，再次排序完成整个数组的排序。这个不断缩小的增量，就构成了一个增量序列。

从理论上说，只要一个数组时递减的，并且最后一个值是1，都可以作为增量序列使用。但目前从数学上来说，无法证明哪个序列是“最好的”，即找不到一组序列使希尔排序时间复杂度最优。

六、归并排序

对于给定的一组数据，利用递归与分治技术将数据序列划分为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。

举个例子

原始数组：[35,63,48,9,86,24,53,72]

分为一半[35,63,48,9]  ,  [86,24,53,72]

再分 [35,63]  [48,9]  ,    [86,24]  [53,72]

数组已经够小了，可以直接排序

[63,35]  [48,9]   , [86,24]  [72,53]

也可以不排序，直接分到一个元素为止，然后合并。

进行合并，在左边和右边的初始位置设置指针。

将两个指针指向的元素进行比较，将小的填入数组（应该专门设一个数组保存结果）

然后指针后移，直到左右数组都被遍历完。

合并 [63,48,35,9]   [86,82,53,24]

再合并 [86,82,63,53,48,35,24,9]

七、堆排序

许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将他们排序，很多时候，我们每次只需要操作数据中最大或最小元素，那么就有一种基于二叉堆的数据结果可以提供支持。

所谓二叉堆，是一个完全的二叉树结构，同时满足堆的性质：即子结点的键值或索引总是小于或者大于它的父结点。在一个二叉堆中，根结点总是最大（或最小）结点，这样的堆我们称之为最大（小）堆。

堆排序算法就是抓住了这一特点，每次都取堆顶的元素，然后将剩余的元素重新调整为最大（最小）堆，最终得到排序的序列。

八、计数排序

计数排序是一种排序时不比较元素大小的排序算法。

计数排序对一定范围内的整数排序时速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限定对于整数排序、并且待排序元素值分布比较连续、跨度小的情况。

如果一个数组里所有元素都是整数而且都在0~k以内。那对于数组里每一个元素来说，如果知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

九、桶排序

桶排序是计数排序的升级版

桶排序的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶在分别排序（可以使用其他的排序算法或者递归调用桶排序）。

3A网络致力为您提供高品质的云计算产品，目前获取游戏、金融、直播、视频、门户、下载、站长平台等行业主流平台支持。采用多种方式进行数据保护，防止数据丢失，承诺99.95%的服务可用性，数据可靠性不低于99.9999%，网络处理能力满足各种业务应用要求各项性能指标业界领先。用户之间100%的完全网络隔离，确保数据安全以及极致的隐私性。

十、基数排序

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9的数字组成。基数排序按照从右往左的顺序依次将每一位都当作一次关键字，然后按照该关键字对数组的元素入桶，每一轮入桶都基于上一轮入桶的结果；完成所有位入桶后，整个数组就达到了有序状态。基数排序也是一种无序比较的算法。