当前位置: 代码迷 >> 数据结构与算法 >> 关于快速排序性能的疑点
  详细解决方案

关于快速排序性能的疑点

热度:2108   发布时间:2013-02-26 00:00:00
关于快速排序性能的疑问
快排理论上平均速度是所有排序中最快的,但在实际应用当中,由于高级语言的限制,要用递归来实现。这样一来就有了重复调用函数的时间开销,快速排序的速度优势就没有了啊。

stdlib中的qsort函数内部是不是通过递归实现的?
快速排序

------解决方案--------------------------------------------------------
“重复调用函数”主要是内存的开销,对时间的影响并不大;另外,“归并排序”是“以牺牲空间的代价减少时间”的典型排序,所以经常用于外部排序(因为硬盘的大小几乎是无限的);如果要考虑节省内存,堆排序是比较合适的算法,整个排序只需要一个全局变量int temp用于swap操作;还有,快速排序是可以转换为非递归的,方法是自顶向下对空间树进行层序遍历;归并也可以转换为非递归,通过队列操作,自底向上依次生成父节点,直到根节点,空间树接近完全二叉树。
------解决方案--------------------------------------------------------
>这样一来就有了重复调用函数的时间开销,快速排序的速度优势就没有了啊。
我笑笑。

>stdlib中的qsort函数内部是不是通过递归实现的?
libc里的qsort没看过。STL的sort你能想到的库都是。
------解决方案--------------------------------------------------------
在现有的软件中,高级语言实现快速排序,鲜有用递归来实现的。
------解决方案--------------------------------------------------------
引用:
在现有的软件中,高级语言实现快速排序,鲜有用递归来实现的。

+1

虽然没有实际调研过,但是高级语言就为什么非要用递归实现呢?感觉很站不住脚。
  相关解决方案
本站暂不开放注册!
内测阶段只得通过邀请码进行注册!