冒泡排序优化：

  1. 每轮交换后，下一轮的交换次数减一。
  2. 记录每轮交换后最后一次交换的索引，在这之后的都已排序好。如果索引为零，代表未发生交换，已排好序。

选择排序：

将集合分为两个部分：有序和无序，每次排序选择无序部分中的最小/大值放入有序集合中，每次排序只需要交换一次。

一般来说，对于有序度低的集合，选择排序快于冒泡排序，因为交换次数少，但是选择排序不稳定，会改变原集合中相同元素的位置，而冒泡排序是稳定的。

插入排序

初始时，将集合第一个元素当作有序，往后扩展有序的范围，依次往后面进行比较，将被比较的元素插入合适的位置，其他的元素往后移，因为它没有改变原集合中相同元素的位置，所以它也是稳定的。

一般来说，插入排序的性能优于选择排序，假设情景为从扑克牌堆中取牌，对于插入排序，你手中的牌就相当于有序区间，而选择排序需要在牌堆中找最小/大值。同时，由牌堆的例子可以看出，插入排序可以在排序的同时插入新的数据，而选择排序需要排序前就把所有数据给好。

快速排序

1. 单边排序（lomuto洛穆托分区方案）

  1. 选择最右元素作为基准点元素
  2. j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
  3. i 指针维护小于基准点元素的边界，也是每次交换的目标索引
  4. 最后基准点与 i 交换，i 即为分区位置
  5. 修改上下索引边界，递归调用

2. 双边排序

  1. 选择最左元素作为基准点元素
  2. j 指针负责从右向左找比基准点小的元素，i 指针负责从左向右找比基准点大的元素，一旦找到，二者交换，直至 i，j 相交
  3. 最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置

注意：

  1. 一定是j先动，如果i先动，最后i与j重合的时候指向的指就会比基准点大
  2. 内层循环一定要加上i<j，如果不加，对于j前面的值都比基准点小的情况下，i就会大于j，导致基准点交换后左边会有一个值大于基准点

2.特点：

  1. 平均时间复杂度O(nlog2n)，最坏时间复杂度O(n²)
  2. 数据量较大时，优势非常明显
  3. 属于不稳定排序