今天这篇文章将学习冒泡排序 和 快速排序，它们都属于交换排序。

什么是交换排序呢？

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

冒泡排序的原理:
每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第2 位上的数
归位，依次类推下去。如果有n个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。
而“每一趟”都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪-
位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

冒泡排序到底是如何排序的呢？

具体是怎么移动的呢？

假设有下面一组无序数组，我们要对它进行升序排序，具体实现过程如下：

按照冒泡排序的思想，我们要把相邻的元素两两比较，根据大小来交换元素的位置。

首先让 6 和 9 比较，发现 6 比 9 要小，因此元素位置不变。

第二趟冒泡排序：

首先让 6 和 7 比较，发现 6 比 7 要小，因此元素位置不变。

继续让 7 和 9 比较，发现 7 比 9 要小，因此元素位置不变。

第三趟冒泡排序：

按照以上步骤，第三轮过后的状态如下：

第四趟冒泡排序：

第七趟冒泡排序：

第八趟冒泡排序：

到此为止，所有元素都是有序的了，这就是冒泡排序的整体思路。

让我们回顾一下刚才描述的排序细节，仍然以 6,9,7,4,10,3,2,8 这个数组为例；

当排序算法分别执行到第六、第七、第八轮的时候，数列状态如下：

很明显可以看出，自从经过第六轮排序，整个数列已然是有序的了。可是我们的排序算法仍然 “兢兢业业” 地继续执行第七轮、第八轮。

这种情况下，如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。

因此，我们进行一个优化的方法：就是设置一个 flag

如果在本轮排序中有元素进行交换，则说明数列无序，如果已经排序了那么设置为 1；
如果在本轮排序中，没有元素进行交换，则说明数列有序，那么设置为 0。

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

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

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

4. 稳定性：稳定

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

将区间按照基准值划分为左右两半部分的常见方式有：

（1）hoare 版本

（2）挖坑法

（3）前后指针法

Hoare 版本的单趟排序的基本步骤如下：

1）选出一个 key，一般是最左边或是最右边的值。
2）定义一个 L 指向最左边的位置，定义一个 R 指向最右边的位置，L 从左向右走，R 从右向左走。（需要注意的是：若选择最左边的数据作为 key，则需要 R 先走；若选择最右边的数据作为 key，则需要 L 先走）。
3）我们以选取最左边的值作为 key 为例子，那么 R 先走，在走的过程中，若 R 遇到小于 key 的数，则停下，L 开始走，直到 L 遇到一个大于 key 的数时，将 L 和 R 的内容交换，R 再次开始走，如此进行下去，直到 L 和 R 最终相遇，此时将相遇点的内容与 key 交换即可。

经过一次单趟排序，最终使得 key 左边的数据全部都小于 key，key 右边的数据全部都大于 key。

这个方法的精华在于：单趟排完以后，key 已经放在正确的位置，那么左边有序，右边有序，那么我们整体就有序了

图解演示

第一趟排序：

首先，R 先走，从右往左找比 key 小的值，第一个数 10 大于 6，继续走。

第二个数 8 大于 6，继续走。

此时，L 开始走，从左往右找比 key 大的值，第一个数 1 小于 6，继续走。

第二个数，2 小于 6，继续走。

然后我们再将 key 的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，因为这种序列可以认为是有序的。

代码实现

特性总结

时间复杂度：O ( N ∗ l o g N )

基本思路

挖坑法的单趟排序的基本步骤如下：

1）选出一个数据（一般是最左边或是最右边的）存放在 key 变量中，在该数据位置形成一个坑。
2）定义一个 L 指向最左边的位置，定义一个 R 指向最右边的位置，L 从左向右走，R 从右向左走（若在最左边挖坑，则需要 R 先走；若在最右边挖坑，则需要 L 先走）。
3）假设我们这里选取最左边的作为坑位，那么就是 R 先走，在走的过程中，若 R 遇到小于 key 的数，则将该数放入坑位，并在此处形成一个坑位，这时 L 再向后走，若遇到大于 key 的数，则将其放入坑位，又形成一个坑位，如此循环下去，直到最终 L 和 R 相遇，这时将 key 放入坑位即可。
经过一次单趟排序，最终也使得 key 左边的数据全部都小于 key，key 右边的数据全部都大于key。

挖坑法相比于 hoare 法，更好理解：

1）不需要理解为什么最终相遇位置比 key 小
2）不需要理解为什么左边做key，右边先走

图解过程

假设我们有下面这样一组无序数组，我们选择最左边的值把它存放到变量 key 中，然后在该位置形成一个坑位，还是 L 指向最左边，R 指向最右边：

第一趟排序

首先，R 先走，从右往左找比 key 小的值，第一个数 10 大于 6，继续走。

第二个数 8 大于 6，继续走。

第三个数 5 小于 6，停下来，把 5 扔到坑位里面去，然后在 R 位置形成新的坑位：

此时，L 开始走，从左往右找比 key 大的值，第一个数 1 小于 6，继续走。

第二个数 2 小于 6，继续走。

可以看到 6 已经放到了正确的位置上面。

然后也是将 key 的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

代码实现

特性总结

时间复杂度：O ( N ∗ l o g N )

基本步骤

前后指针法的单趟排序的基本步骤如下：

1）选出一个 key，一般是最左边或是最右边的。
2）起始时，prev 指针指向序列开头，cur 指针指向 prev+1。
3.1）若 cur 指向的内容小于 key，则 prev 先向后移动一位，然后交换 prev 和 cur 指针指向的内容，然后 cur 指针 ++；
3.2）若 cur 指向的内容大于 key，则 cur 指针直接++。如此进行下去，直到 cur 指针越界，此时将 key 和 prev 指针指向的内容交换即可。
经过一次单趟排序，最终也能使得 key 左边的数据全部都小于 key，key 右边的数据全部都大于 key。

图解过程

此时 cur 指向的元素是 7，大于 6，那么 cur 指针直接向后走一步，prev 指针不动。

接着 cur 又指向 9，大于 6，那么 cur 指针继续向后走一步，prev 指针还是不动。

此时 cur 指向的元素 8 大于 6，那么 cur 指针直接向后走一步，prev 指针不动。

接着 cur 指向的元素 10 大于 6，那么 cur 指针直接向后走一步，prev 指针不动。

此时 cur 指针已经越界，那么我们将 prev 指向的元素 5 与 key 进行交换：

此时，元素 6 已经回到了正确的位置上面。

然后还是将 key 的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作。

代码实现

特性总结

时间复杂度：O ( N ∗ l o g N )

三数取中

假设，当待排序列本就是一个有序的序列时，我们若是依然每次都选取最左边或是最右边的数作为 key，那么快速排序的效率将达到最低：

其实，对快速排序效率影响最大的就是选取的 key，若选取的 key 越接近中间位置，则则效率越高。

为了避免这种极端情况的发生，于是出现了三数取中：

三数取中，当中的三数指的是：最左边的数、最右边的数以及中间位置的数。
三数取中就是取这三个数当中，值的大小居中的那个数作为该趟排序的 key。
这就确保了我们所选取的数不会是序列中的最大或是最小值了。

代码示例

注意：这个三数取中函数可以放在任意一个单趟排序版本中，上面代码我是放在了前后指针法的代码中。

小区间优化

我们可以看到，就算是上面理想状态下的快速排序，也不能避免随着递归的深入，每一层的递归次数会以 2 倍的形式快速增长。

为了减少递归树的最后几层递归，我们可以在 快速排序的主体框架中 设置一个判断语句，当序列的长度小于某个数的时候就不再进行快速排序，转而使用其他种类的排序。

小区间优化若是使用得当的话，会在一定程度上 加快 快速排序的效率，而且待排序列的长度越长，该效果越明显。

代码示例

上面我们使用递归实现了快速排序的主框架，可以发现与二叉树前序遍历规则非常像，所以在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

如果在这里想把主框架改为非递归实现的话，那么需要借助前面学到的一种数据结构 栈，我们先来看一看非递归实现的思路：

1）先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
2.1）当栈不为空时，读取栈中的信息（一次读取两个，一个是 L，另一个是 R），然后调用某一版本的单趟排序，排完后获得了 key 的下标，然后判断 key 的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的 L 和 R 入栈；
2.2）若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
反复执行步骤 2，直到栈为空为止。

代码示例

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

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

4. 稳定性：不稳定