各种排序算法的比较_各种排序算法的最好最坏情况

1.时间复杂度
直接插入排序法：平均情况是O（n^2），最好情况是O（n），最坏情况是 O（n^2），辅助空间是O（1）
冒泡排序法：平均情况O（n^2），最好的情况是O（n），最坏的情况是 O（n^2），辅助空间是O（1）
希尔排序法：平均情况是O（nlog2 n）~O（n^2），最好的情况是 O（n^{1.3），最坏的情况是O（n}2），辅助空间是O（1）。
快速排序法：平均情况，最好的情况都是O（nlog2 n），最坏的情况是O（n^2）（已经有顺序了），辅助空间是O（log2 n）-O（n）
简单选择排序法：平均情况，最好情况，最坏情况都是 O（n^2），辅助空间是O（1）。
堆排序：平均情况，最好情况，最坏情况都是 O（nlog2 n），辅助空间是O（1）。
归并排序：平均情况，最好情况，最坏情况都是O（nlog2 n），辅助空间为O（n）。
基数排序：平均情况，最好情况，最坏情况都是O（d（n+m）），辅助空间为O（m）

从平均情况来看：
1.直接插入排序，冒泡排序，简单选择排序属于一类，时间复杂度为O（n^2），其中直接插入排序方法最常用，特别是对已按关键码基本有序的序列
2.堆排序，归并排序，快速排序属于第二类，时间复杂度为O（nlog2n），其中快排是目前认为最快的一种排序，在待排序个数较多的情况下，归并排序比堆排序要快
3.希尔排序是对直接插入排序的一种改进，相当于分治，时间复杂度就介于O（nlog2 n）与O（n^2）之间。
4.基数排序是借助多关键码进行桶排序的思想对单关键码进行排序，例如先按个位收集，再按十位收集，最后成为有序序列。在子关键码的个数d较少的时候可以看成线性排序。

从最好情况来看
直接插入和冒泡排序的时间复杂度最好，都是O（n），其他的排序算法的最好情况和平均情况一样

从最坏情况来看，快速排序的时间复杂变成了O（n^2），直接插入排序和冒泡排序虽然与平均情况相同，但是系数大约增加了一倍，所以运行速度将会降低到一半。最坏情况对直接选择排序，堆排序，归并排序，基数排序影响并不大。

由此可知，最好情况下，直接插入和冒泡是最好的，平均情况下，快速排序是最好的。
最坏的情况下，堆排序和归并排序是最好的。

从空间复杂度来看
可以分成四类，归并排序为一类，其空间复杂度为O（n），快速排序也为一类，其空间复杂度为O（log2 n）~O（n），基数排序为一类，其空间为O（m），其他排序为一类，空间复杂度为O（1）。

从稳定性来看
可以分为两类，稳定的：直接插入排序，冒泡排序，归并排序，基数排序
不稳定的：希尔排序，快速排序，简单选择排序，堆排序

从待排序的个数来看
如果是小规模数据，用简单排序比较合适，因为这时候的O（nlog2n）与O（n^2）相差不大。但是规模大的时候就尽量使用改进的排序算法比较好。

综合上述考虑
1.当待排序的记录个数n较大的时候，关键码分布随机，而且对稳定性不做要求的时候，采用快速排序较好。
2.当待排序的记录个数n较大的时候，内存空间允许，而且要求排序稳定，采用归并排序为好。
3.当待排序的记录个数n较大的时候，关键码分布出现正序或者逆序的时候，而且对稳定性不作要求，可以使用归并排序或者堆排序。
4.当待排序的记录个数n较大的时候，而只能找到最小的前几个记录，采用堆排序或者简单选择排序。例如在堆排序中，想找到序列中第k大的记录，则需要O(n+klog2n)时间，如果k很小，这会快很多。
5.当待排序记录个数n较小的时候（如小于100），记录又基本有序，而且要求稳定，采用直接插入排序。例如在一个已经排好序的序列上略做修改后，最好用插入排序恢复有序，就像抽牌。
6.当待排序的记录个数n较小的时候，记录所含的数据项较多，所占的存储空间较大的时候，可以采用简单选择排序法。
7.快速排序和归并排序在n较小的时候，性能还不如直接插入排序，因此在实际的应用中，我们可以将它们混合使用。例如在快速排序中划分的子序列小于某个数值，转而调用直接排序，或者对待排序的序列先逐段进行直接插入排序，然后利用归并操作进行两两归并处理。