的三个值中位数策略 [英] median of three values strategy
问题描述
一些身体能告诉我什么是三个策略中位数来选择快速排序枢轴值。
Can some body tell me that what is the median of three strategy to select the pivot value in quick sort.
我读它在网络上，但无法弄清楚它究竟是？以及如何它比随机快速排序好。
I am reading it on the web but couldn't figure it out what exactly it is? And also how it is better than the randomized quick sort.
感谢
推荐答案
三中位数有你看看数组的第一个，中间和最后一个元素，然后选择这三个要素作为支点的中间值。
The median of three has you look at the first, middle and last elements of the array, and choose the median of those three elements as the pivot.
要拿到三中位数的全效，这也是很重要的排序的这三个项目，而不仅仅是使用中位数为支点 - 这并不影响什么选为枢轴在当前迭代，而能/会影响什么作为在接下来的递归调用，这有助于限制了一些初始排序的不良行为（一说原来是特别糟糕，在许多情况下，支点是一个数组多数民众赞成排序，除了具有阵列的高端最小的元素（或在低端市场最大的元素），例如：
To get the "full effect" of the median of three, it's also important to sort those three items, not just use the median as the pivot -- this doesn't affect what's chosen as the pivot in the current iteration, but can/will affect what's used as the pivot in the next recursive call, which helps to limit the bad behavior for a few initial orderings (one that turns out to be particularly bad in many cases is an array that's sorted, except for having the smallest element at the high end of the array (or largest element at the low end). For example:
相比采摘枢轴随机：
- 在这可以确保一个常见的情况（完全排序的数据）仍然保持最佳状态。
- 这是比较难操纵入给最坏的情况。
- 一个PRNG通常是比较慢的。
这是第二点可能蕴藏着更多的解释。如果您使用的是明显的（兰特（））的随机数生成器，它很容易（许多情况下，无论如何）为某人安排的元素，它会不断地选择差支点。这可能是类似的东西，可以排序一个已经进入了一个潜在的攻击者，谁可能会通过让您的服务器浪费了大量的时间对数据进行排序安装DoS攻击数据的Web服务器是一个严重问题。在这样的情况下，你的可以的使用真正的随机种子，或者你可以有，而不是使用兰特（）自己的PRNG - 或者你用用中位数三种，其中也有其他的优点提及。
That second point probably bears a bit more explanation. If you used the obvious (rand()) random number generator, it's fairly easy (for many cases, anyway) for somebody to arrange the elements so it'll continually choose poor pivots. This can be a serious concern for something like a web server that may be sorting data that's been entered by a potential attacker, who could mount a DoS attack by getting your server to waste a lot of time sorting the data. In a case like this, you could use a truly random seed, or you could include your own PRNG instead of using rand() -- or you use use Median of three, which also has the other advantages mentioned.
在另一方面，如果你使用了足够的随机数生成器（例如，硬件发生器或计数器模式加密），它可能的更多的困难，迫使不好的情况下绝对比的中位数三个选择。同时，实现随机性这一水平通常具有相当多的它自己的开销，所以除非你真的指望在这种情况下被攻击，它可能不值得（如果你这样做，它可能是价值至少考虑的替代方案，保证了O（N日志N）最坏的情况下，如合并排序或堆排序。
On the other hand, if you use a sufficiently random generator (e.g., a hardware generator or encryption in counter mode) it's probably more difficult to force a bad case than it is for a median of three selection. At the same time, achieving that level of randomness typically has quite a bit of overhead of its own, so unless you really expect to be attacked in this case, it's probably not worthwhile (and if you do, it's probably worth at least considering an alternative that guarantees O(N log N) worst case, such as a merge sort or heap sort.
这篇关于的三个值中位数策略的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
