数据结构十种排序算法总结

部分来自https://mp.weixin.qq.com/s/feQDjby4uYGRLbYUJq7Lpg?

总结

首先先上张图 好好记住

排序算法大全

图中的名字的意思：
n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
这么一看感觉很乱 我们分下类，瞬间感觉很简单

1. 冒泡排序：冒泡排序的思想很简单，就是数组两两元素交换 ，从第一个元素交换到最后一个元素，所以他的时间复杂度为n的平方。
   因为相同的元素不会交换，所以他是稳定的。
   当然这个排序也是可以优化的，如果某一轮没有元素进行交换，那就说明已经排好序了。
   同样因为复杂度比较高，所以只适用于量级比较小的数据。
2. 选择排序：选择排序就是不断从未排序的序列里面选择最大或者最小的元素放在头或者尾，所以他的时间复杂度为n的平方，而且不管在什么情况，复杂度一般不会波动，所以是一种比冒泡排序更好的排序算法。
   如果用数组实现的话是不稳定的，用链表实现的话是稳定的，一般默认数组实现。
   因为复杂度的关系，所以也是只适用于小数据。
3. 插入排序：插入排序就是不断地选择未排序好的数据插入到排序好的数据中它应该在的位置。时间复杂度也是n的平方。
   这个选择他应有的位置是通过在已排序好的数组里面从后向前遍历到不大于他的位置来完成的，所以也是稳定排序。
   插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
   在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。
4. 希尔排序：希尔排序的思想就是设置一组增量的序列，然后按着增量把数组分为不同的子数组进行插入排序，注意这个增量最后一定要是1。希尔排序的时间复杂度由不同的增量序列决定，从n的1.3到2波动。
   虽然插入排序是稳定的，但是希尔排序是多次插入排序，所以是不稳定的。
   Shell排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀--快速排序O(n㏒n)快。在大量数据面前，Shell排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。
5. 归并排序：该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。时间复杂度是nlogn。
   因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。
   归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度O(n)使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。
6. 快速排序：快速排序也是用分治的思想，先选一个基准，然后把小的都放他前面，大的都放他后面，不断递归。时间复杂度是nlogn
   快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。
   快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。
7. 堆排序：堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
   堆排序存在大量的筛选和移动过程，属于不稳定的排序算法。
   堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。
   建立的话从非叶子结点开始调整，每次和他的子节点做对比，将最大的换上来，然后依次进行调整，最后堆顶就是最大的元素。然后把最大的元素和最后的叶子结点交换继续调整。
8. 计数排序：其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数，个人理解为哈希计数法。时间复杂度是O(n+k)，空间复杂度也是O(n+k)。
   计数排序是稳定排序。
   排序目标要能够映射到整数域，其最大值最小值应当容易辨别。例如高中生考试的总分数，显然用0-750就OK啦；又比如一群人的年龄，用个0-150应该就可以了，再不济就用0-200喽。另外，计数排序需要占用大量空间，它比较适用于数据比较集中的情况。
9. 桶排序：它的工作原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。
   可以看出，在分桶和从桶依次输出的过程是稳定的。但是，由于我们在对每个桶进行排序时使用了其他算法，所以，桶排序的稳定性依赖于这一步。如果我们使用了快排，显然，算法是不稳定的。
   桶排序可用于最大最小值相差较大的数据情况，但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
10. 基数排序：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。时间复杂度为n*k
    如果出现相同的元素，则保持他们在原始数组中的顺序。可见，基数排序是一种稳定的排序。

然后最后三种非比较的算法的区别是：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值