好了。终于把3-way qsort完成标准优化了:) - Programming版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

Programming版 - 好了。终于把3-way qsort完成标准优化了:)

相关主题
● 一道C＋＋面试编程题	● C++如何pass一个变量给一个函数，但是函数声明却没有这个变量？
● 有人能解释一下这段C++代码吗	● code question
● 帮帮看看这段tree insertion	● c＋＋一个问题
● [合集] 如何得到一个指向STL元素的指针？	● 问个MATRIX的题
● 靠。Sedgewick这3w-qsort算法居然还有bug!	● 请教一个字符串比较排序的问题
● stl的nth_element的复杂度是不是O(N)？	● about STL functor and function pointers
● Do the two statements cost the same amount of time?	● 一个C的void指针的问题
● 大家看看这个简单的qsort排序的问题	● tail call strange behavior on cl.exe

相关话题的讨论汇总
话题: qsort话题: glibc话题: insertion话题: optimized话题: 优化

进入Programming版参与讨论

(共1页)

a***n
发帖数: 1616

优化部分基本是抄的glibc qsort的，不过glibc的写得太烂了，只要了它的idea ...
1. median-3 pivot
2. 3-way partition with optimized tight inner loops
3. non-recursive, w/ log(n) stack, always finish shorter partition first
4. qsort + final insertion sort hybrid with THRESH=5
5. optimized tight inner loop for final insertion sort

(共1页)

进入Programming版参与讨论

相关主题
● tail call strange behavior on cl.exe	● 靠。Sedgewick这3w-qsort算法居然还有bug!
● 请教如何使用qsort() to sort string.	● stl的nth_element的复杂度是不是O(N)？
● 再问个C++模板问题	● Do the two statements cost the same amount of time?
● C++ optimization question	● 大家看看这个简单的qsort排序的问题
● 一道C＋＋面试编程题	● C++如何pass一个变量给一个函数，但是函数声明却没有这个变量？
● 有人能解释一下这段C++代码吗	● code question
● 帮帮看看这段tree insertion	● c＋＋一个问题
● [合集] 如何得到一个指向STL元素的指针？	● 问个MATRIX的题

相关话题的讨论汇总
话题: qsort话题: glibc话题: insertion话题: optimized话题: 优化

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天