冒泡排序

冒泡排序的思路是从数组的第一个元素开始，依次比较相邻的两个元素，如果不符合我们想要的排序顺序则交换位置。通过n-1次循环即可得到排好序的数组。

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j + 1 < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
    }
  }
}

因为冒泡排序在第k(k < n)轮循环可能就已经有序，因此可以设置一个flag去判断是否已经有序：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let isSwapped = false
    for (let j = 0; j + 1 < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        isSwapped = true
      }
    }
    if (!isSwapped) break
  }
}

通过上面的思想，其实当一轮冒泡排序结束后，可能第[m, n - 1]的元素已经是有序的，因此其实只需要对[0, m - 1]的元素进行排序即可。同样，也设置一个flag，不过这里是记录已经有序的子数组的起始下标。

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1;) {
    let lastSwapedIndex = 0
    for (let j = 0; j + 1 < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        lastSwapedIndex = j + 1 // [j + 1, arr.length - 1]的元素已经有序
      }
    }
    i = arr.length - lastSwapedIndex // 这里 i 可以看成每轮循环后已经有序的元素数量
  }
}

选择排序

选择排序的思路是遍历数组，每次从剩余元素中选择最大/最小的值和当前元素交换位置，直至所有元素都排好序，时间复杂度为O(n^2)。

class SelectionSort {
  constructor () {
    if (new.target) throw new Error('this is a static class.')
  }
  static sort (list) {
    if (list.length < 2) return list
    for (let i = 0; i < list.length; i ++) {
      let minIndex = i
      for (let j = i + 1; j < list.length; j ++) {
        if (list[j].compareTo(list[minIndex]) < 0) minIndex = j
      }
      this._swap(list, minIndex, i)
    }
    return list
  }
  // 从后往前遍历
  static reverseSort (list) {
    if (list.length < 2) return list
    for (let i = list.length - 1; i >= 0; i --) {
      let maxIndex = i
      for (let j = i - 1; j >= 0; j --) {
        if (list[j].compareTo(list[maxIndex]) > 0) maxIndex = j
      }
      this._swap(list, maxIndex, i)
    }
    return list
  }
  static _swap (list, i, j) {
    let temp = list[i]
    list[i] = list[j]
    list[j] = temp
  }
}
module.exports = SelectionSort

插入排序

插入排序的思路是每次找到当前元素应该插入的相对位置，然后将元素放在其正确的位置。插入排序的复杂度为O(n^2)。但是对于有序数组插入排序的复杂度为O(n)。

class InsertionSort {
  static sort (list) {
    for (let i = 0; i < list.length; i ++) {
      for (let j = i; j > 0 && list[j].compareTo(list[j - 1]) > 0; j --)
        this._swap(list, j, j - 1)
    }
    return list
  }
  // 通过平移的方式优化代码
  static betterSort (list) {
    for (let i = 0; i < list.length; i ++) {
      let t = list[i], j // 保存当前需要插入的元素下标
      for (j = i; j > 0 && t.compareTo(list[j - 1]) > 0; j --)
        list[j] = list[j - 1] // 当不是最终需要插入的位置时将元素向后平移一位
      // 寻找到最终位置后
      list[j] = t
    }
    return list
  }
  // 从后往前遍历
  static reverseSort (list) {
    for (let i = list.length - 1; i >= 0; i --) {
      let t = list[i], j
      for (j = i; j < list.length - 1 && t.compareTo(list[j + 1]) > 0; j ++)
        list[j] = list[j + 1]
      list[j] = t
    }
    return list
  }
  static _swap (list, i, j) {
    let temp = list[i]
    list[i] = list[j]
    list[j] = temp
  }
}
module.exports = InsertionSort

归并排序

归并排序的思路在于每次将数组平分成两份，然后分别对两个数组进行排序，再合并两个有序数组即可。归并排序的时间复杂度是O(nlogn)。同样，对于有序数组，归并排序的时间复杂度为O(n)。

class MergeSort {
  constructor () {
    throw new SyntaxError('cannot use new operator.')
  }
  static sort (list) {
    this._sort(list, 0, list.length - 1)
    this._cacheList = [...list]
  }
  static _sort (list, l, r) {
    if (l >= r) return
    // const m = Math.floor((l + r) / 2) 推荐使用下面的方式计算m，防止数据超出JavaScript可表示的整数范围
    const m = l + Math.floor((r - l) / 2)
    this._sort(list, l, m)
    this._sort(list, m + 1, r)
    if (list[m] > list[m + 1]) this._merge(list, l, m, r) // 如果 list[m] <= list[m + 1] 说明list已经有序了
  }
  static _merge (list, l, m, r) {
    for (let i = l; i <= r; i ++) this._cacheList[i] = list[i]
    let k = l, i = l, j = m + 1
    for (; k <= r; k ++) {
      if (i > m) {
        list[k] = this._cacheList[j]
        j ++
      } else if (j > r) {
        list[k] = this._cacheList[i]
        i ++
      } else if (this._cacheList[i] <= this._cacheList[j]) {
        list[k] = this._cacheList[i]
        i ++
      } else {
        list[k] = this._cacheList[j]
        j ++
      }
    }
    // or
    // while (i <= m || j <= r) {
    //   if (i > m) {
    //     list[k++] = this._cacheList[j]
    //     j ++
    //   } else if (j > r) {
    //     list[k++] = this._cacheList[i]
    //     i ++
    //   } else if (this._cacheList[i] < this._cacheList[j]) {
    //     list[k++] = this._cacheList[i]
    //     i ++
    //   } else {
    //     list[k++] = this._cacheList[j]
    //     j ++
    //   }
    // }
  }
}
module.exports = MergeSort

快速排序

快速排序的思想是每次确定其中一个元素的最终位置，直至所有元素都在其最终位置上。快速排序是一个不稳定的排序算法，其时间复杂度为O(n*2)，但是由于实际情况下这种最差的情况几乎不可能出现，因此通常使用期望来权衡其性能，快速排序的期望是nlogn。

单路快速排序

根据上述过程，我们假设需要确定位置的元素的下标为l，则通过一轮循环，l对应的元素已经在其最终位置，其下标为lt，它将数组分成了两个子数组。对这两个子数组重复上述操作，又将确定两个元素的位置，以此类推直至所有元素有序。

class QuickSort {
  constructor () {
    throw new SyntaxError('cannot use new operator.')
  }
  static sort (list) {
    this._sort(list, 0, list.length - 1)
  }
  static _sort (list, l, r) {
    if (l >= r) return
    const p = this._partition(list, l, r)
    this._sort(list, l, p - 1)
    this._sort(list, p + 1, r)
  }
  static _partition (list, l, r) {
    let lt = l
    for (let i = l + 1; i <= r; i ++) {
      if (list[i] < list[l]) {
        lt ++
        this._swap(list, i, lt)
      }
    }
    this._swap(list, l, lt)
    return lt
  }
  static _swap (list, i, j) {
    const temp = list[i]
    list[i] = list[j]
    list[j] = temp
  }
}

上述算法存在一个问题，由于每次都是确定第一个元素的位置，如果对完全有序的数组进行排序，则时间复杂度会达到O(n*2)。原因是当数组有序时，每个元素都在其最终位置上，因此当每轮循环后，都会将原有数组分成一个空数组和一个数组长度为原数组长度减1的数组。这样导致递归执行的次数等于数组长度。解决方法是每次执行_partition的时候先取一个大小为[l, r]之间的随机整数random，然后将list[l]和list[random]进行交换。修改_partition如下：

static _partition (list, l, r) {
  const random = Math.floor(Math.random() * (r - l + 1)) + l
  this._swap(list, l, random)
  let lt = l
  for (let i = l + 1; i <= r; i ++) {
    if (list[i] < list[l]) {
      lt ++
      this._swap(list, i, lt)
    }
  }
  this._swap(list, l, lt)
  return lt
}

双路快速排序

上面的优化虽然一定程度上避免了有序数组造成的性能倒退问题，但是如果整个数组的值都相同，则性能依旧会倒退。这时我们可以使用双路快速排序，使用两个指针从数组的两端遍历，有效的避免了这个问题。

class QuickSort {
  constructor () {
    throw new SyntaxError('cannot use new operator.')
  }
  static sort (list) {
    this._sort(list, 0, list.length - 1)
  }
  static _sort (list, l, r) {
    if (l >= r) return
    const p = this._partition(list, l, r)
    this._sort(list, l, p - 1)
    this._sort(list, p + 1, r)
  }
  static _partition (list, l, r) {
    const random = Math.floor(Math.random() * (r - l + 1)) + l
    this._sqrt(list, l, random)
    let lt = l + 1
    let gt = r
    while (true) {
      while (list[lt] < list[l]) lt ++
      while (list[gt] > list[l]) gt --
      if (lt >= gt) break
      this._sqrt(list, lt, gt)
      lt ++
      gt --
    }
    this._sqrt(list, l, gt)
    return gt // 注意这里返回的是 gt
  }
  static _swap (list, i, j) {
    const temp = list[i]
    list[i] = list[j]
    list[j] = temp
  }
}

三路快速排序

双路快速排序虽然解决了数组元素相同的问题，但是没有对这种情况做特殊处理。事实上当元素相同的时候无需做交换的操作，此时排序的复杂度为O(n)。

class QuickSort {
  constructor () {
    throw new SyntaxError('cannot use new operator.')
  }
  static sort (list) {
    this._sort(list, 0, list.length - 1)
  }
  static _sort (list, l, r) {
    if (l >= r) return
    const [lt, gt] = this._partition(list, l, r)
    this._sort(list, l, lt - 1)
    this._sort(list, gt, r)
  }
  static _partition (list, l, r) {
    const random = l + Math.floor(Math.random() * (r - l + 1))
    this._swap(list, l, random)
    let cur = l + 1
    let lt = l
    let gt = r + 1
    while (cur < gt) {
      if (list[cur] < list[l]) {
        lt ++
        this._swap(list, lt, cur)
        cur ++
      } else if (list[cur] > list[l]) {
        gt --
        this._swap(list, lt, gt)
      } else {
        cur ++
      }
    }
    this._swap(list, l, lt)
    return [lt, gt]
  }
  static _swap (list, i, j) {
    const temp = list[i]
    list[i] = list[j]
    list[j] = temp
  }
}

希尔排序

对于插入排序来说，性能消耗主要在于元素之间的比较，在极端情况下，例如数组最小的元素位于末尾，则此次循环比较次数为数组长度减1，为了减少比较次数，可以考虑增大比较步长，不再固定移动1位而是将相隔h的元素进行比较。通过减小h至1完成整个排序。每次排序完一次后数组的逆序对都会减少，从而在h等于1时(相当于插入排序)需要比较的次数大大减少。这就是希尔排序。

function shellSort (list) {
  let h = list.length >>> 1
  while (h >= 1) {
    for (let start = 0; start < h; start ++) {
      for (let i = start + h; i < list.length; i += h) {
        let cur = list[i]
        let j
        for (j = i; j - h >= 0 && cur < list[j - h]; j -= h) {
          list[j] = list[j - h]
        }
        list[j] = cur
      }
    }
    h = h >>> 1
  }
  return list
}

上面的方法是将原数组按照h分成了多个子数组，通过分别对子数组排序一步步使得数组变得有序，最终完成排序。另一种方式是无需特意分成多个子数组，只需每隔h个元素进行比较即可：

function shellSort (list) {
  let h = list.length >>> 1
  while (h >= 1) {
    for (let i = h; i < list.length; i ++) {
      let cur = list[i]
      let j
      for (j = i; j - h >= 0 && cur < list[j - h]; j -= h) {
        list[j] = list[j - h]
      }
      list[j] = cur
    }
    h = h >>> 1
  }
  return list
}

上述两种方式的h都是每次减小一半，实际h的大小和希尔排序算法性能息息相关，通过将h的值变为1、4、7、10...这种规律可以提高算法性能：

function shellSort (list) {
  let h = 1
  while (h < list.length) h = 3 * h + 1
  while (h >= 1) {
    for (let i = h; i < list.length; i += h) {
      let cur = list[i]
      let j
      for (j = i; j - h >= 0 && cur < list[j - h]; j -= h) {
        list[j] = list[j - h]
      }
      list[j] = cur
    }
    h = Math.floor(h / 3)
  }
  return list
}

希尔排序处理一些中等大小的数组和其他时间复杂度更小的排序算法性能相差不大，且无需使用递归，因此在处理实际问题时如果数据规模不大可以考虑使用希尔排序。