总结
| sorting algorithm | English Name | how | general rule | best case | worst case |
|---|---|---|---|---|---|
| 冒泡排序 | bubble sort | 比较相邻两个元素，如果逆序就交换；接着比较下一对相邻两个元素。循环两次，外层循环结尾不断缩短。 | 只是作为一种知识来了解，很少有实际应用？？？ 适合小数据 |
O(n) ordered |
O(n^2) anti-ordered |
| 选择排序 | selection sort | 选择当前最小的元素，放到已经排序好的末尾 | 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。 | O(n^2)都一样 | O(n^2)都一样 |
| 插入排序 | insertion sort | 扑克牌打法：对于未排序数据，在已排序序列从后向前扫描，找到相应位置并插入。 | 插入排序由于O( n2 )的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的实现中，当待排数组长度小于47时，会使用插入排序。 | O(n) ordered |
O(n^2) anti-ordered |
| 堆排序 | heapsort | 使用堆这个数据结构来排序 | 堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。 | O(nlogn)都一样 | O(nlogn)都一样 |
| 快排 | quicksort | 分治法，选择一个基准，把小于这个基准的放在左边，大于这个基准的放在右边 | 快速排序对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。 快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。 |
O(n) 当顺序的时候 |
O(n^2) 当逆序的时候 |
| 归并排序 | merge sort | 分治思想 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 |
归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度O(n) 使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。 | O(nlogn)都一样 | O(nlogn)都一样 |
| 计数排序 | Bucket Sort/ Bin sort | 核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序 | 要求输入的数据必须是有确定范围的整数。 | O(n+k)都一样 | O(n+k)都一样 |
| 基数排序 | Radix Sort | 将整数按位数切割成不同的数字，然后按每个位数分别比较。 | 基数排序要求较高，元素必须是整数，整数时长度10W以上，最大值100W以下效率较好，但是基数排序比其他排序好在可以适用字符串，或者其他需要根据多个条件进行排序的场景，例如日期，先排序日，再排序月，最后排序年 ，其它排序算法可是做不了的。 | O(n*k)都一样 | O(n*k)都一样 |
- python内置的sort使用的是什么
Python里sort（）的排序算法–Timsort简介_山水无间道的博客-CSDN博客_python sort排序算法Tim排序，是一种合并排序和插入排序的结合体。
在排序长度低于64的时候采取：插入排序 。
高于64的时候采取一种改良的归并排序。查找升序和降序的部分（Run），进行反转/合并
选择排序为什么是不稳定的？
理解选择排序的不稳定性_小黄鸭zm的博客-CSDN博客_选择排序为什么不稳定
假设nums[0] == nums[1] > nums[2]
交换之后是nums[2], nums[1], nums[0]。原来下标为0和1的顺序被破坏了
排序算法之间的比较
应用最广泛的是快排
快速排序的最坏运行情况是 O(n²)，比如说顺序/逆序数列的快排。但它的平摊期望时间是 O(nlogn)。对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
为什么不是归并排序？
快排O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。
归并排序在任何情况下的时间复杂度都是O(nlogn)，但是归并排序不是原地排序的，需要借助额外的存储空间。
归并排序的空间复杂度为什么是O(n)，而不是O(nlogn)？因为递归代码的
空间复杂度并不能像时间复杂度那样累加，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。归并排序的空间复杂度_鸭梨山大哎的博客-CSDN博客_归并排序空间复杂度
