分區方法

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中的值的中間，則這是一種非常快速的排序方法。