数据结构-各种排序算法效率对比图

为了加深记忆，制作此图。

根据此表整理了排序对比图，其中

1. 柱状图蓝色表示是稳定的，柱状图黄色表示不稳定的；

2. 柱状图中间的数字表示时间复杂度，红色字体表示最差时，黑色字体表示平均复杂度；

3. 柱状图虚线表示最差时的时间复杂度，因为冒泡排序，交换排序，选择排序的最差和平均时间复杂度是一样的，都是O(n^2)，所以图中看不见虚线；

4. 实线柱状图，即平均时间复杂度，效率从低到高依次是： 

 冒泡排序 ≈ 交换排序 ≈选择排序 < 插入排序 <Shell排序 <堆排序 < 归并排序 <快速排序

    大多数情况下，快速排序效率最高，但如果数据已经基本有序的情况下，效率退化到O(n^2)。

1. 冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法，时间复杂度为O(n^2)。

2. 插入排序是把序列中的值插入一个已经排序好的序列中，直到该序列的结束。它比冒泡排序快2倍。一般不适合数据量比较大的场合或数据重复比较多的场合。

3. 选择排序在实际应用中和冒泡排序基本差不多，使用较少。

4.  Shell排序是通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数，其中Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起快速排序，归并排序，堆排序慢很多。但shell算法比较简单，特别适合数据量在5000以下且性能要求不是很高的场合。

5.   归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，由于它需要一个额外的数组，因此需要比堆排序多一些内存空间。

6. 6

   快速排序是利用分治法，进行大规模递归的算法，具体见下面步骤：      步骤1： 如果不多于1个数据，直接返回。      步骤2：般选择序列最左边的值作为支点数据。

        步骤3： 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。

       步骤4： 对两边利用递归排序数列。快速排序比大部分排序算法都要快。尽管在某些特殊的情况下有比快速排序快的算法，但通一般情况下，没有比它更快的。

   快速排序比大部分排序算法都要快。尽管在某些特殊的情况下有比快速排序快的算法，但通一般情况下，没有比它更快的。

7. 7

     堆排序将是所有的数据先建成一个堆，如大顶堆（最大的数据在堆顶），然后将堆顶数据和序列的最后一个数据交换，然后重新建堆，交换数据，依次下去，就可以排序所有的数据。由于不需要大量的递归或者多维的暂存数组，因此这对于数据量非常巨大的序列是很合适的，比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。

数据来源：

java排序源码下载：

http://download.csdn.net/detail/tanggod/6919719

最后

以上就是唠叨小白菜为你收集整理的数据结构-各种排序算法效率对比图的全部内容，希望文章能够帮你解决数据结构-各种排序算法效率对比图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。