目录
Ⅰ.冒泡排序
1.基本思想
2.代码实现
3.总结
Ⅱ.快速排序
1.基本思想
2.hoare法
基本思想：
代码实现:
3.挖坑法
基本思想：
代码实现：
4.前后指针法
基本思想：
代码实现：
5.非递归法
基本思想：
代码实现：
6.快速排序的优化与改进
7.总结
反复交换相邻两个元素的位置，从而把待排序的元素序列逐个比较并按照大小重新排列。
即
我们分析发现
在每一趟中都要保证本趟中最大的值处于本次的最后，保证排出升序
我们用以下代码来验证
有
1. 冒泡排序是一种非常容易理解的排序2. 时间复杂度： O(N^2)3. 空间复杂度： O(1)4. 稳定性：稳定
任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右 子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。
图示如下
因此我们可以构建一个基础的通用代码模型
基本思想：
首先从数列中选择一个基准值。
将数列中小于等于基准值的元素放在基准值的左侧，将大于等于基准值的元素放在基准值的右侧。
对左右两个子序列分别重复以上步骤，直到每个子序列只剩下一个元素为止。
即
代码实现:
我们用如下代码测试
有
基本思想：
选取数组的一个元素作为基准值 key。
从数组的最右端开始向左遍历，寻找第一个小于 key 的元素，将其挖出，并将该位置留空作为坑。
从数组的最左端开始向右遍历，寻找第一个大于 key 的元素，将其挖出，并填入刚刚留下的坑中。
重复执行步骤 2 和步骤 3，直到左右两个遍历指针相遇。
将基准值 key 填入最后一个坑中，此时 key 左侧所有元素都小于 key，右侧所有元素都大于等于 key。
对左右两个子序列分别重复以上步骤，直到每个子序列只剩下一个元素为止。
图示如下
代码实现：
还是采用hoare法的检测代码，有
基本思想：
选取数组的一个元素作为基准值 pivot。
设置两个指针，一个指向数组的第一个元素（即前指针），一个指向 pivot（即后指针）。
从前指针开始向后遍历，寻找第一个大于等于 pivot 的元素。
将该元素与后指针指向的元素交换位置，后指针向后移动一个位置。
重复执行步骤 3 和步骤 4，直到前指针遍历到数组的最后一个元素。
将 pivot 与后指针指向的元素交换位置，此时 pivot 左侧所有元素都小于 pivot，右侧所有元素都大于等于 pivot。
对左右两个子序列分别重复以上步骤，直到每个子序列只剩下一个元素为止。
图示如下
代码实现：
还是采用上述的代码检验，有
基本思想：
将待排序序列的起始位置和结束位置压入栈中，作为当前子序列的起始状态。
循环执行以下操作，直到栈为空：
- 弹出栈顶元素，得到当前子序列的起始位置 left 和结束位置 right。
- 对子序列进行一次快速排序，得到基准值的位置 keyi。
- 如果基准值左侧子序列元素个数大于 1，将左侧子序列的起始位置 left 和结束位置 keyi-1 压入栈中，等待下一轮排序。
- 如果基准值右侧子序列元素个数大于 1，将右侧子序列的起始位置 keyi+1 和结束位置 right 压入栈中，等待下一轮排序。
排序完成后，原序列就变成了有序的序列。
图示如下
在对0(begin)到9(end)进行一趟快排后，得到一个基准值key，如果左右两侧元素均不只有一个元素，将key左侧起始位置(begin)到key-1(end)位置压栈，再将key右侧keyi+1(begin)位置到右侧结束位置(end)压栈
代码实现：
我们使用如下的检测代码
有
其实对于快速排序，我们可以发现它的整体是类似于完全二叉树的形式，而在数据量较少时，我们可以采取效率更高的插入排序，即