methods - 分区方式

Question

我试图准确地理解这种方法的作用，它说它假设“不断交换最外面的错误定位对”。我把它放入一个程序并尝试了不同的数组，但结果对我来说毫无意义，这到底是做什么的

partition(A, p)  
A: array of size n, p: integer s.t. 0 <= p < n

 1. swap(A[0],A[p])

 2. i <- 1, j <- n − 1

 3. while i < j do

 4.   while A[i] <= A[0] and i < n do

 5.     i <- i + 1

 6.   while A[j] > A[0] and j > 0 do

 7.     j <- j − 1

 8.   if i < j then

 9.     swap(A[i], A[j])

10. swap(A[0], A[j])

11. return j

Answer 1

此伪代码实现的算法是快速排序算法的分区阶段。它将排列数组，使所有小于或等于A[p]的值在左侧，所有较大的值在右侧。它返回的索引j是左侧的最后一个索引，它是A[j]equals A[p]。

如果您不熟悉快速排序，其目的是使用此分区算法将数组拆分为“小”和“大”部分，并对每个部分进行递归排序。由于小数组已被安排在数组中的大数组之前，因此数组已排序。如果p选择得当，使其A[p]接近 中值的中间A，这是一种非常快速的排序方法。