插入排序效率问题

Question

var arr = [3, 44, 38, 35, 34, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 5, 50, 48, 18];

function insertionSort1(array) {

  for (var i = 1; i < array.length; i++) {

    var key = array[i];

    var j = i - 1;

    while (j >= 0 && array[j] > key) {

      array[j + 1] = array[j];

      j--;

    }

    array[j + 1] = key;

  }

  return array;

}

var log = console.log.bind(console)

log(insertionSort2(arr));

console.time('time');

for (var z = 0; z < 5000000; z++) {

  insertionSort3(arr);

}

console.timeEnd('time')

这个插入排序,为什么while条件 j >= 0 && array[j] > key 和array[j] > key && j >= 0
运行时间差很多

Answer 1

&&：只要前者不匹配，就不会继续往后执行了。 而判断 j >= 0 花费的时间比 array[j] > key 花费的时间少。你要是换成 &，二者花费时间就差不多了