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

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可能会更耗时，因为有更多的操作。