分区方式
我试图准确理解这个方法的作用，它说它应该 “继续交换最外面位置错误的对”。我把它放入一个程序中 并尝试了不同的数组，但结果对我来说毫无意义，这到底是做什么的
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
I am trying to understand exactly what this method does, it say its suppose to
"Keep swapping the outer-most wrongly-positioned pairs". I put this into a program
and tried different array but the result make no sense to me, what exactly does this do
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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
此伪代码实现的算法是快速排序算法的分区阶段。它将排列数组，使所有小于或等于
A[p]的值位于左侧，所有较大的值位于右侧。它返回索引j，即A[j]等于A[p]的左侧的最后一个索引。如果您不熟悉快速排序，其目的是使用此分区算法将数组分为“小”和“大”部分，并对每个部分进行递归排序。由于数组中小数组被安排在大数组之前，因此数组已排序。如果
p选择适当，使得A[p]接近A中值的中间，这是一种非常快速的排序方法。The algorithm this pseudocode implements is the partitioning phase of the quicksort sorting algorithm. It will arrange the array so that all values smaller than or equal to
A[p]are at the left and all larger values at the right. It returns the indexjthat is the last index of the left side for whichA[j]equalsA[p].If you are not familiar with quicksort, the intent is to use this partition algorithm to split the array into "small" and "large" parts and recursively sort each part. Since the small ones had been arranged to come before the large ones in the array, the array gets sorted. If
pis picked appropriately so thatA[p]is close to the middle of the values inA, this is a very fast sorting method.