algorithm - ヒープソートを使用して0と1の配列をソートする時間の複雑さは?

Question

ヒープソートで、すべての要素が 0 と 1 だけの場合、通常のランダム要素の場合と比べて複雑さは変わりますか?

Answer 1

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;
}