冒泡排序

bubbleSort.js

/**
 * 冒泡排序，此方法每次固定头部最小值，即前方为有序区，时间复杂度O(n^2)，空间复杂度O(1)
 * @param {Array} arr 需要排序的数据源
 * @return {Array} arr 排序后数组
 */
function bubbleSort(arr) {
  var len = arr.length;
  for(var i=0; i<len-1; i++) {
    for(var j=i+1; j<len; j++) {
      if(arr[i] > arr[j]) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

function bubbleSort2(arr) {
  var len = arr.length;
  var isSorted = false; // 如果一次循环中未进行数据交换则已经有序
  var cursor = 0; // 游标，每次循环后方有序区则不需要进行比较
  while(!isSorted) {
    isSorted = true;
    for(var i=0; i<len-1-cursor; i++) {
      if(arr[i+1] < arr[i]) {
        isSorted = false; // 需要交换，还是非有序的
        var temp = arr[i+1];
        arr[i+1] = arr[i];
        arr[i] = temp;
      }
    }
    cursor += 1;
  }
  return arr;
}