algorithm - 快速排序二进制数组

Question

我想知道有多少比较，在最坏的情况下，Quicksort 需要对 size 的二进制数组进行排序n。
我无法找出这个问题的最坏情况。[0 1 0 1 0 1..]?
干杯，
eo

score 1 · Accepted Answer

不完全是快速排序，但如果你想对二进制数组进行排序，你可以在 O(n) 中完成。只需计算您有多少个 1 和 0，然后按照您想要的顺序写入。

例如，对于以下数组：

[0 1 0 1 0 1 1]

您可以在 O(n) 中计算出三个 0 和四个 1。然后你只需先用三个 0 重写你的数组，然后再用四个 1 重写你的数组。

score 0 · Accepted Answer

对包含少量唯一键的数组进行排序在实践中很常见。当唯一键的数量为 O(1) 时，人们想要一种适应 O(n) 时间的算法。在您的情况下，只有两个唯一的键。

QuickSort 平均为 O(nlogn)，但在最坏的情况下为 O(n^2)，对于你的情况，我已经在这个数组上测试了快速排序算法，数组 [ 0 1 1 0 1 0 1 0 0 0 1 0 1 ]的长度是13元素，算法需要170迭代来排序数组，即n^2.

这个 O(n) 算法的伪代码：

let n0 <- 0;
for i=0  to lenght(A)
    if A[i] == 0
        A[n0] = 0;
        ++n0

for i=n0 to lenght(A)
    A[i] = 1

2 回答 2