基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。一趟冒泡排序就可以把一个最大或者最小的挑出来，走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。
算法步骤：
-
比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
-
针对所有的元素重复以上的步骤，除了最后一个。
-
针对所有的元素重复以上的步骤，除了最后两个。
-
重复持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O()
- 空间复杂度：O(1)
- 稳定性：稳定
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。将区间按照基准值划分为左右两半部分的常见方式有以下三种：
hoare版本
下图为hoare版本单趟排序的动图：
实现代码：
完整快速排序思路分析：
- 这样的一趟排序返回的这个meeti其实就是a[key]在数组中的正确位置，而且a[key]的左边都是小于a[key]的数了，a[key]的右边都是大于a[key]的数了，相当于这样的一种状态[begin, keyi-1] keyi [keyi+1, end]，
- 下一次就是再把[begin, keyi-1]这个区间和 [keyi+1, end]放入单趟排序函数里再排序，直到这个区间最后只剩下0个或者一个元素的时候递归就可以停止了。
实现代码：
下面是三个优化选key逻辑：
1、随机选一个位置做key
2、针对有序，选定中间值做key
3、 三数取中。在待排序数列的第一个位置和中间位置以及最后一个位置 选出中间值，然后把这个中间值与第一个位置交换。
这里我们就选择第三种方法的三数取中
实现代码：
挖坑法
前后指针版本
- 当a[cur] < a[keyi]的时候就我们就让prev++然后交换cur的和prev的值，只不过前面他俩处在同一个位置交换之后也没有效果，
- 当a[cur] >= a[keyi]的时候就只++cur
- cur越界了就停止然后交换prev和key的值返回prev的位置即可。
这样key也找到了他自己正确的位置并且key的左边也是小于key的值，右边都是大于key的值。
实现代码：
快速排序完整代码链接