optimization - 在（快速）排序时，分区而不是旋转有显着的好处吗？

Question

在快速排序算法的每个阶段，都会选择一个枢轴，并且数据被双向划分为低于和高于该枢轴的元素（并且一些平局打破等于它）。

现在，每次旋转都需要传递数据。此外，枢轴作为中值元素的相对位置的方差非常高。取而代之的是，可以想象取 k 个元素的样本 iid ，并将数据划分为 k+1 个部分，使用样本元素作为不同部分的边界。虽然有些部分可能太小或太大，但大多数都应该没问题；其余的将需要一些更正（例如通过计数），但这应该是可行的。

我没有在（二进制）快速排序上尝试过这种方法，但想知道这种方法是否在实践中被使用，以及这样做是否真的有好处。

PS - 如果你能谈谈并行化的适应性（在 CPU 上使用 AVX-512，使用 Xeon Phi，使用 GPU 等）——那将非常有帮助。

标签： optimizationquicksortidioms