algorithm - Quicksort面试题: Quicksort run three times

Question

我最近面试的一个问题:

Consider an array with n elements which is divided into three parts:

A[1] .....................................................A[n]
part1(m1)..........part2(m2)......... part3(m3)

Then quick sort is run on it three times as follows:

QuickSort(A[m1+1.....n])
QuickSort(A[1.....m1+m2])
QuickSort(A[m1+1.....n])

Under what condition is the array is sorted?

a) m1>m2
b) m1<m2
c) m1>=m2
d) m1=m2=m3

我的答案是 m1>m2 但现在我怀疑 m1>=m2 是否也是正确的。这样对吗？

Answer 1

我声称 m1 <= m2是充分必要的。

1. 如果是这样，我们可以确定第一个之后m2 m1 + 1 ... n 中的最小数字部分位于 1 ... m1 + m2 内字首。 m2 >= m1 ，因此 m1最小的数字在 1 ... m1 + m2 内字首。这意味着在第二次运行之后，他们将处于正确的位置。 m1 + 1 ... n 中发生了什么并不重要部分原因是无论如何它将在上次运行期间修复。

2. 如果不是这样，很容易构建一个反例:{3, 3, 1, 2, 2}, m1 = m3 = 2, m2 = 1。

   <

这意味着:b)和d)都是正确的。