摘要 Abstract
考虑一种使用 $K\in\mathbb{N}$ 个轴元素的多轴快速排序算法,通过将未排序列表划分为 $K+1$ 个有序子列表以递归处理这些子列表。在划分阶段,存在多种策略。我们关注的是在标准随机模型下(即列表为由不同元素组成的均匀排列)使期望关键比较次数最小的策略。我们推导出当 $K\in\mathbb{N}$ 时关键比较次数的期望和方差的渐近展开式,并证明所有 $K\in\mathbb{N}$ 的极限定律,其中收敛适用于所有(指数)矩。对于 $K\leq 4$,我们还限定了 Wasserstein 和 Kolmogorov--Smirnov 距离下的收敛速率。我们的期望分析基于经典的随机 $m$-元查找树结果。对于其余结果,则利用组合考虑使收缩方法适用。
We consider a multi-pivot QuickSort algorithm using $K\in\mathbb{N}$ pivot elements to partition a nonsorted list into $K+1$ sublists in order to proceed recursively on these sublists. For the partitioning stage, various strategies are in use. We focus on the strategy that minimizes the expected number of key comparisons in the standard random model, where the list is given as a uniformly permuted list of distinct elements. We derive asymptotic expansions for the expectation and variance of the number of key comparisons as well as a limit law for all $K\in\mathbb{N}$, where the convergence holds for all (exponential) moments. For $K\le 4$ we also bound the rate of convergence within the Wasserstein and Kolmogorov--Smirnov distance. Our analysis of the expectation is based on classical results for random $m$-ary search trees. For the remaining results, combinatorial considerations are used to make the contraction method applicable.