1

如果我们已经得到一个随机数组，为什么还要使用随机快速排序？

如果我们收到一个随机数组，并且每次都选择最后一个条目作为枢轴，那是否仍然被认为是随机的，因为我们收到了一个随机数组，我们甚至不知道每个条目的位置。

常规快速排序的伪代码

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

PARTITION(A, p, r)
x = A[r]
i = p − 1
for j = p to r − 1 do
     if A[j] ≤ x then
          i = i + 1
          exchange A[i] and A[j]

exchange A[i + 1] and A[r]
return i + 1

随机快速排序的伪代码

RandPartition(A, p, r)
     i = Random(p, r)
     exchange A[r] and A[i]
     return PARTITION(A, p, r)

RandQuicksort(A, p, r)
     if p < r then
     q = RandPartition(A, p, r)
     RandQuicksort(A, p, q − 1)
     RandQuicksort(A, q + 1, r)
4

1 回答 1

1

是的，如果已知输入是随机的，那么额外的随机化将毫无用处。确定性地选择最后一个元素作为枢轴也一样好。

如果不知道输入是随机的，那么图片就完全不同了。

于 2013-11-01T22:25:23.083 回答