起泡排序

  1.     //起泡排序算法
  2.     #bubbleSort(lo, hi) {
  3.          const bubble = (lo,hi) => {
  4.             let sorted = true //整体有序标志
  5.             while (++lo < hi) {
  6.                 if (this.#elem[lo - 1] > this.#elem[lo]) {
  7.                     sorted = false
  8.                     [this.#elem[lo - 1],this.#elem[lo]] = [this.#elem[lo],this.#elem[lo - 1]]
  9.                 }
  10.             }
  11.             return sorted
  12.         }
  13.         while (!bubble(lo, hi--));
  14.     }

改进版本
image.png

稳定性

image.png
image.png

归并排序

历史与发展

它是第一个可以在最坏情况下依然保持O(nlogn)运行时间的确定性排序算法

有序向量的二路归并

与起泡排序通过反复调用单趟扫描交换类似，归并排序也可以理解为是通过反复调用所谓二
路归并（2-way merge） 算法而实现的。所谓二路归并，就是将两个有序序列合并成为一个有序
序列。
image.png
二路归并算法在任何时刻都只需载入两个向量的首元素进行比较

分治策略

实例

二路归并接口的实现

归并时间

推广

排序时间