这两种冒泡排序执行速度差在那里？

Question

function bubbleSort1(arr) {      var i = arr.length - 1,
        j, tmp;      while (i !== 0) {        var p = 0;        for (j = 0; j < i; j++) {          if (arr[j] > arr[j + 1]) {
            tmp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = tmp;
            p = j;
          }
        }
        i = p;
      }      return arr
    }    var sort = function (arr) {      var len = arr.length;      var i = 0, j = 0, temp;      for (i = 0; i < len; i++) {        for (j = 0; j < len - i - 1; j++) {          if (arr[j] > arr[j + 1]) {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
          }
        }
      }      return arr;
    }

这两种冒泡排序执行速度差10倍 差在那里。

Answer 1

因为你每一次冒泡，可能将不止一个数放到他对应的位置，第一种算法可以避免不必要的冒泡

Answer 2

你说的差了10倍不正确。首先从算法复杂在的角度来说都是O(n2)。bubbleSort1在冒泡时做了一些优化，即当数组为[3,1,2,7,8,9]这种情况时。后面7,8,9是有序的，后面冒泡将不再考虑后面的那一块。所以;1、当数组为部分有序时，方法bubbleSort1可以节省一些时间。2、当数组为逆序数组时，例如[5,4,3,2,1]这种，方法bubbleSort1可能会更耗时，因为有更多的操作。