algorithm - 使用堆排序对 0 和 1 数组进行排序的时间复杂度是多少？

Question

在堆排序中，如果所有元素都只有0和1，那么与随机元素的正常情况相比，复杂度会发生变化吗？

Answer 1

堆排序的运行时间由两部分决定：

• 构建堆所需的时间为 Θ(n)，以及
• 从堆中连续删除元素所需的时间，（通常）是 Θ(n log n)

在所有值都是 0 或 1 的情况下，第二步的运行时间仍有可能是 Ω(n log n)。假设你的堆的结构是底层的所有元素都是 1，其他层的所有元素都是 0。在这种情况下，前 n 次你删除一个元素并尝试修复堆，你会将 1 交换到根，然后不断地将 1 向下冒泡到树的底部，这需要时间 Θ(日志 n)。这意味着完成的功至少为 Ω(n log n)。

正如@SRF 指出的那样，这里没有必要使用堆排序。您可以使用计数排序将数组排序为 Θ(n) 时间。

希望这可以帮助！

Answer 2

堆排序保证任何输入的时间复杂度为 O(n*lgn)。

但是，如果您知道数组的所有元素都仅限于“0”和“1”，那么您可以以 O(n) 时间复杂度对该数组进行排序。（尝试“计数排序”）

Answer 3

您不应该使用 HeapSort 对 1 和 0 进行排序。有一个 O(n) 算法。（使用 ES6）

const sorter = (input) => {
  let left = 0, right = input.length -1;
  while (right > left) {

    while (input[left] === 0 && right > left){
        left ++;
    }
    while (input[right] === 1 && right > left){
        right --;
    }
    if (input[left] > input[right]) {
      [input[left], input[right]] = [input[right], input[left]];
    }
    right--; left++;
  }
  return input;
}