网站开发最后五个阶段/互联网营销师证书含金量

       排序算法可以说是非常重要的基础算法。可能一般少有单独排序的任务，但是大多任务都是基于排序算法的。现在，对于排序算法进行一个总结。

       排序算法可以分为两种，第一种是比较类的，第二种是非比较类的。比较类算法包括插入排序，选择排序，快速排序等等方法；非比较类算法包括计数排序，桶排序和计数排序。

       比较类的算法都是元素之间的相互比较然后更换位置等等，其时间复杂度一般是$O(n^2)$，最优的时间复杂度一般是$O(nlogn)$，但是耗费的空间很少。而非比较类的算法是通过一些函数映射然后在分类的，其算法复杂度可以达到$O(n)$，但是会耗费很多的空间。

非比较类

       非比较类的排序算法都是通过某一个映射函数将数字映射到一个容器里，然后比较的。算法的时间复杂度比较低，一般都是$O(n)$级别的，但是空间复杂度就很高了，也是$O(n)$级别的。

       其中，计数排序法只能操作整数，将最大值和最小值之间所有的整数设置为容器，加入最大为5，最小为0，那我们就设置6个桶：0，1，2，3，4，5，6，然后将数字一次遍历放到桶中去。由于桶和桶之间的顺序我们已经知道了，所以我们只需要合并即可。计数排序法非常适合于有范围的比较，比如我们的评分是1-5分，这种比较使用计数排序效率非常高，耗费的空间也不是很大，并且几乎没有浪费。

       桶排序是计数排序的升级版，它不再是每一个整数设置为一个容器了，它把整个数列的范围设置成若干个容器，比如将0-10设置成5个容器，那么就是0-2，2-4，4-6，6-8，8-10。然后堆每个容器进行排序，这里调用的排序算法哪个都可以，当然最终的效率也和调用的算法有关。桶排序就可以操作小数了。桶排序默认数字的分布是服从均匀分布的，这时候的效果就很好了。

       基数排序有一种按照重要性排序的意思，我们先按照个位数排序，然后是十位数，依次类推，这样的排序方法处理负数和小数比较麻烦。当数字分布不是均匀分布的时候，基数排序不会有那么多浪费的空间。

比较类

$O(n^2)$级别的算法

       说到$O(n^2)$的算法，一般指的都是冒泡排序法，插入排序法和选择排序法。这三个排序方法思想比较简单，但是他们之间比较容易混淆。虽然他们的时间复杂度很高，但是空间复杂度很低，都是$O(1)$，也就是说可以在数列本身的空间上进行排序。

低于$O(n^2)$的算法

       时间复杂度低于$O(n^2)$的算法也借鉴了$O(n^2)$的思想。希尔排序是第一个突破$O(n^2)$的排序算法，希尔排序法是插入排序的改进，插入排序法一次只能移动一个位置，但是希尔排序法在最开始ide时候一次可以移动多个位置，其最好的时间复杂度大概在$O(n^1.3)$左右。

       归并排序利用了分而治之的思想，先将序列分成两个字串，然后在递归调用排序，最后只需要合并到一起就好了，其算法的时间复杂度是$O(nlogn)$，空间富足度比较高，是$O(n)$。

       快速排序法是我们使用最多的一种排序方法，其思想是选定一个标准，然后标准两边放置是比基准小和比基准大的数，然后递归调用快速排序法，最终直到排好序。其时间复杂度是$O(nlogn)$，达到了排序算法时间复杂度的下界，但同时它也会占据$O(nlogn)$的额外空间。

       堆排序从效果上来看是最好的了，其时间复杂度不论输入数据如何都是$O(nlogn)$，并且空间复杂度是$O(1)$。但是在实现的时候使用了堆的概念，实现起来不是很方便，应用范围目前也赶不上快速排序。

算法详解和python实现

冒泡排序法
选择排序法
插入排序法
希尔排序法
归并排序法
快速排序法
堆排序法
计数排序法
桶排序法
基数排序法