分区方法

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

伪代码实现的算法是quicksort sorting algorithm的分区阶段。它将排列数组，使得所有小于或等于A[p]的值位于左侧，而所有大于右侧的值。它返回的索引j是A[j]等于A[p]的左侧的最后一个索引。

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