冒泡排序

function exchange(arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

function bubbleSort(arr) {
  // 遍历 length - 1 轮
  for (let i = 0; i < arr.length - 1; i++) {
    // 每轮遍历个数为 length - i
    for (let j = 0; j < arr.length - 1 - i; j++) {
      // 从小到大
      if (arr[j + 1] < arr[j]) {
        exchange(arr, j, j + 1)
      }
    }
  }
  return arr
}

测试

console.log(bubbleSort([5, 8, 6, 3, 9, 2, 1, 7]))
console.log(bubbleSort([3, 4, 2, 1, 5, 6, 7, 8]))

优化: 如果已经有序，提前返回

function bubbleSort(arr) {
  // 遍历 length - 1 轮
  for (let i = 0; i < arr.length - 1; i++) {
    let exchanged = false
    // 每轮遍历个数为 length - i
    for (let j = 0; j < arr.length - 1 - i; j++) {
      // 从小到大
      if (arr[j] > arr[j + 1]) {
        exchange(arr, j, j + 1)
        exchanged = true
      }
    }
    // 如果没有交换过，表示已经有序，提前结束
    if (!exchanged) {
      break
    }
  }
  return arr
}

优化: 根据交换位置, 缩小无序边界

function bubbleSort(arr) {
  let lastExchangeIndex = 0
  let sortBoard = arr.length - 1
  // 遍历 length - 1 轮
  for (let i = 0; i < arr.length - 1; i++) {
    let exchanged = false
    // 每轮遍历个数为 length - i
    for (let j = 0; j < sortBoard; j++) {
      // 从小到大
      if (arr[j] > arr[j + 1]) {
        exchange(arr, j, j + 1)
        exchanged = true
        lastExchangeIndex = j
      }
    }
    // 如果没有交换过，表示已经有序，提前结束
    if (!exchanged) {
      break
    }
    // 每次交换结束，缩小无序边界
    sortBoard = lastExchangeIndex
  }
  return arr
}

优化: 每一轮, 两端交换

function bubbleSort(arr) {
  const length = arr.length
  let lastExchangeIndex = 0
  let rightSortBoard = length - 1
  let leftSortBoard = 0

  for (let i = 0; i < arr.length / 2; i++) {
    let exchanged = false

    for (let j = leftSortBoard; j < rightSortBoard; j++) {
      // 从小到大
      if (arr[j + 1] < arr[j]) {
        exchange(arr, j, j + 1)
        exchanged = true
        lastExchangeIndex = j
      }
    }
    // 如果没有交换过，表示已经有序，提前结束
    if (!exchanged) {
      break
    }
    rightSortBoard = lastExchangeIndex

    exchanged = false
    for (let j = rightSortBoard; j > leftSortBoard; j--) {
      if (arr[j - 1] > arr[j]) {
        exchange(arr, j - 1, j)
        exchanged = true
        lastExchangeIndex = j
      }
    }
    if (!exchanged) {
      break
    }
    leftSortBoard = lastExchangeIndex
  }
  return arr
}