排序算法全景：冒泡 / 选择 / 插入

// 运行环境：Node.js 14+
// 保存为 dsa-l17.js，执行：node dsa-l17.js

// 冒泡：相邻比较，大的往后冒；每轮把最大值推到末尾
function bubbleSort(a) {
  a = a.slice() // 不破坏原数组
  for (let i = 0; i < a.length; i++)
    for (let j = 0; j < a.length - 1 - i; j++)
      if (a[j] > a[j + 1]) [a[j], a[j + 1]] = [a[j + 1], a[j]]
  return a
}

// 选择：每轮选最小值，放到已排区末尾
function selectionSort(a) {
  a = a.slice()
  for (let i = 0; i < a.length; i++) {
    let min = i
    for (let j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j
    [a[i], a[min]] = [a[min], a[i]]
  }
  return a
}

// 插入：像理牌，把当前元素插到前面已排区的正确位置
function insertionSort(a) {
  a = a.slice()
  for (let i = 1; i < a.length; i++) {
    const key = a[i]
    let j = i - 1
    while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j-- }
    a[j + 1] = key
  }
  return a
}

console.log(bubbleSort([5, 2, 4, 1, 3]))     // [1,2,3,4,5]
console.log(selectionSort([5, 2, 4, 1, 3]))   // [1,2,3,4,5]
console.log(insertionSort([5, 2, 4, 1, 3]))   // [1,2,3,4,5]