带3路分区的Quicksort [英] Quicksort with 3-way partition

问题描述

什么是具有3路分区的QuickSort？

What is QuickSort with a 3-way partition?

推荐答案

为数组拍照：

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0

一个两个分区快速排序会选择一个值，例如4，并将每个大于4的元素放在数组的一侧，然后另一边的每个元素小于4。像这样：

A two partition Quick Sort would pick a value, say 4, and put every element greater than 4 on one side of the array and every element less than 4 on the other side. Like so:

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5

A 三个分区快速排序将选择两个值进行分区并以这种方式拆分数组。让我们选择4和7：

A three partition Quick Sort would pick two values to partition on and split the array up that way. Lets choose 4 and 7:

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9

与常规快速排序相比，这只是一个小变化。

It is just a slight variation on the regular quick sort.

您将继续对每个分区进行分区，直到对数组进行排序为止。
从技术上讲，运行时为nlog ₃ （n），与常规quicksort的nlog ₂ （n）略有不同。

You continue partitioning each partition until the array is sorted. The runtime is technically nlog₃(n) which varies ever so slightly from regular quicksort's nlog₂(n).

这篇关于带3路分区的Quicksort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！