algorithm - 快速排序二进制数组

Question

我想知道在最坏的情况下，快速排序需要多少次比较才能对大小为 n 的二进制数组进行排序。
我无法找出这个问题的最坏情况。 [0 1 0 1 0 1..] ?
干杯，
伊奥

Answer 1

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

例如，对于下面的数组:

[0 1 0 1 0 1 1]

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