==冒泡排序（Bubble Sort）==也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序

直接返回就好

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

5. 什么时候最快
   当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

6. 什么时候最慢
   当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止

📌思路一（Hoare版）

步骤为：

1. 选取基准值

2. 从数组右->左找到比基准值小于或等于的值的下标

3. 从数组右->左找到比基准值大于或等于的值的下标

4. 交换这两下标的值

5. 继续执行二操作，直到操作2与操作3相遇

6. 将基准值放在相遇位置

如下图所示：

📌思路二（挖坑法）

步骤为：

1. 选取基准值后，记录下基准值，假设该下标为空，相当于是个“坑”

2. 从右->左找小于或等于基准值的值，就将该数放入坑中，然后该下标变为新的坑

3. 从左->右找小于或等于基准值的值，就将该数放入坑中，然后该下标变为新的坑

4. 回到步骤2继续执行，直到操作2与操作3所找数相同

5. 将记录下的基准值放回坑里

📌思路三（前后指针）

📌规模较小时的优化

每次递归的时候，数据都是再慢慢变成有序的

当数据量少且趋于有序的时候，我们可以直接使用插入排序进行优化

📌三数取中法

如果在选取基数时我们发现如果基数一边总是没有数，代码的执行次数会增加很多

所以我们的解决方法为：
选取数组第一个数、中间的数、和最后一个数，进行比较

三数中间的数作为每次的基数

寻找中间数代码如下：

使用如下：

实现思路：

• 建立一个栈

• 先让一组数据的起点入栈

• 再让一组数据的终点出栈

• 然后两次出栈，分别作为该数据的起点与终点

• 然后经过我们上面所写的方法进行排序后

• 再将两组数据进行入栈

• 以此循环直到栈为空

🚩代码实现：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4. 重复步骤 3 直到某一指针达到序列尾；

5. 将另一序列剩下的所有元素直接复制到合并序列尾。

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(N)

4. 稳定性：稳定

外部排序：排序过程需要在磁盘等外部存储进行的排序

前提：内存只有 1G，需要排序的数据有 100G

因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M

2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以

3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了