具有相等元素的快速排序算法进程-Java 学习之路

我正在进行算法分配，这需要我用一个相等元素（1（a），1（b），1（c）等数组）显示快速排序算法的进展，其中枢轴是最后一个数组中的元素 . 算法的递归部分令我感到困惑 . 到目前为止，我有进展：

1(a)   1(b)   1(c)   1(d)   [1(e)]
1(a) | 1(b)   1(c)   1(d)    1(e)
1(a)   1(b) | 1(c)   1(d)    1(e)
1(a)   1(b)   1(c) | 1(d)    1(e)
1(a)   1(b)   1(c)   1(d) |  1(e)

在此之后，枢轴将变为1（d）我认为并且进展将与上述相同，除了少一个交换 . 我对左右递归调用如何工作感到困惑 . 阵列“右”侧的元素是否会与自己交换？这个算法什么时候停止？

这是伪代码：

QS(A, p, r):
if p < r
    q = PARTITION(A, p, r)
    QS(A, p, q - 1)
    QS(A, q + 1, r)

PARTITION(A, p, r):
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

p是第一个元素数组，r是最后一个元素 .

谢谢你的帮助 .

1 回答

1
第二个调用， QS(A, q + 1, r) ，在你的情况下将始终是无操作，因为 q 将始终等于 r ，因此调用变为 QS(A, r+1, r) ，由 if p < r guard成为无操作（ p < r 将始终为false） .

所以如果你的数组索引为1,2，...，5; q 的第一个值是5，所以它的第一个递归调用是 QS(A,1,4) ，第二个 - QS(A,6,5) （无操作） .

QS(A,1,4) 也会发生同样的事情 - 它的 q 将是4，而两个调用 - QS(A,1,3) 和 QS(A,5,4) .
```
QA(A,1,5)
   PARTITION(A,1,5) -> 5
   QS(A,1,4)
       PARTITION(A,1,4) -> 4
       QS(A,1,3)
           PARTITION(A,1,3) -> 3
           QS(A,1,2)
               PARTITION(A,1,2) -> 2
                   QS(A,1,1)
                   QS(A,3,2)
           QS(A,4,3)
       QS(A,5,4)
   QS(A,6,5)
```
有趣的代码方式 partition ，从未看到它以这种方式完成 . 我在那里使用 < 而不是 <= ，而不是交换相等的元素 . （当然，在这里，所有掉期都是无操作，在两个相等的指数之间;尽管不是一般情况下） .
回复于 2024-04-29T05:25:42+08:00

具有相等元素的快速排序算法进程

1 回答

相关问题