赞
踩
结论:大部分情况下使用快速排序的效率比归并排序高
看起来归并排序的效率应该比快速排序高啊!
那么为什么会有这样的结论呢?往下看就明白了。
快速排序建立二叉树的时候,我们会采用随机选择pivot基准的方法。
从数字信号系统的概念来看,对于一个线性的波形,使用复合波对其进行采样,会得到复合波的结果。所以我们得到的基准是无序的,这种情况下最坏情况发生的概率极小。
那么就算用了这样的方法,也只是把快速排序的时间效率提高到了o(nlog2n),怎么能得出比归并排序效率高的结论呢?
快速排序对于每一层二叉树,遍历的次数是小于n的,比如说它在第二层就已经确定了一个点的位置,在第三层就已经确定了三个点的位置,在第四层确定了七个点的位置。越向下面的结点遍历,次数越少。
归并排序每次都要将n个数据合并,遍历的次数固定为n。
所以,在每一层的遍历,快速排序是比归并排序要高出0-50%的效率的
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。