排序算法＜8＞:对比与总结_原表是否有序对排序算法影响不大

排序算法对比 表格

 

 

 

 

 

 

 

 

 

 

 

 

注：1. 归并排序的空间复杂度是O(n)，要是用手摇算法来实现原地归并。则空间复杂度是O(1)。

       2.  排序算法稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

 

内排序分类

   1. 插入排序： 直接插入排序 、希尔排序。

    2.选择排序：简单选择排序、堆排序。

    3.交换排序：冒泡排序、快速排序

 

  怎么选择使用哪种内排序算法

      每种排序算法都有优缺点。因此需要根据业务情况，结合算法的优缺点来选择排序算法。

      1. 待排序集合有序或基本有序

            直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

            原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

      2. 当待排序集合数据量比较大时

           选用平均时间复杂度为O(nlogn)的算法。也就是快速排序，归并排序，堆排序。

           快速排序是内部排序中被认为是最好的排序方法，待排序集合数据是随机分布的，使用快速排序比堆排序和归并排序效率高2到3倍。但是快速排序的缺点是不稳定，当集合数据越接近有序时，最坏情况时间复杂度为o(n^2)。

           如果要求稳定性，则使用归并排序。缺点，需要同样大小的的存储空间。

          堆排序，时间复杂度不会出现比较坏的情况。如果对时间复杂度的最坏情况有要求，则使用堆排序。

    3. 当待排序集合数据量比较小时（小于50）

           使用简单选择排序或者直接插入排序。

    4. 数据中重复的数据比较多

          使用归并排序或者希尔排序。          

 

   计数排序、桶排序、基数排序，暂时没研究，不分析。