目录

Ⅰ.冒泡排序

1.基本思想

2.代码实现

3.总结

Ⅱ.快速排序

1.基本思想

2.hoare法

基本思想：

代码实现:

3.挖坑法

基本思想：

代码实现： 

4.前后指针法

基本思想：

 代码实现：

5.非递归法

基本思想：

代码实现：

6.快速排序的优化与改进

7.总结

---

反复交换相邻两个元素的位置，从而把待排序的元素序列逐个比较并按照大小重新排列。

即

我们分析发现

在每一趟中都要保证本趟中最大的值处于本次的最后，保证排出升序

我们用以下代码来验证

 有

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

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

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

4. 稳定性：稳定

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

图示如下 

因此我们可以构建一个基础的通用代码模型

基本思想：

1. 首先从数列中选择一个基准值。

2. 将数列中小于等于基准值的元素放在基准值的左侧，将大于等于基准值的元素放在基准值的右侧。

3. 对左右两个子序列分别重复以上步骤，直到每个子序列只剩下一个元素为止。

即

代码实现:

我们用如下代码测试

 有

基本思想：

1. 选取数组的一个元素作为基准值 key。

2. 从数组的最右端开始向左遍历，寻找第一个小于 key 的元素，将其挖出，并将该位置留空作为坑。

3. 从数组的最左端开始向右遍历，寻找第一个大于 key 的元素，将其挖出，并填入刚刚留下的坑中。

4. 重复执行步骤 2 和步骤 3，直到左右两个遍历指针相遇。

5. 将基准值 key 填入最后一个坑中，此时 key 左侧所有元素都小于 key，右侧所有元素都大于等于 key。

6. 对左右两个子序列分别重复以上步骤，直到每个子序列只剩下一个元素为止。

图示如下

代码实现： 

还是采用hoare法的检测代码，有

基本思想：

1. 选取数组的一个元素作为基准值 pivot。

2. 设置两个指针，一个指向数组的第一个元素（即前指针），一个指向 pivot（即后指针）。

3. 从前指针开始向后遍历，寻找第一个大于等于 pivot 的元素。

4. 将该元素与后指针指向的元素交换位置，后指针向后移动一个位置。

5. 重复执行步骤 3 和步骤 4，直到前指针遍历到数组的最后一个元素。

6. 将 pivot 与后指针指向的元素交换位置，此时 pivot 左侧所有元素都小于 pivot，右侧所有元素都大于等于 pivot。

7. 对左右两个子序列分别重复以上步骤，直到每个子序列只剩下一个元素为止。

图示如下

 代码实现：

还是采用上述的代码检验，有

基本思想：

1. 将待排序序列的起始位置和结束位置压入栈中，作为当前子序列的起始状态。

2. 循环执行以下操作，直到栈为空：

   • 弹出栈顶元素，得到当前子序列的起始位置 left 和结束位置 right。
   • 对子序列进行一次快速排序，得到基准值的位置 keyi。
   • 如果基准值左侧子序列元素个数大于 1，将左侧子序列的起始位置 left 和结束位置 keyi-1 压入栈中，等待下一轮排序。
   • 如果基准值右侧子序列元素个数大于 1，将右侧子序列的起始位置 keyi+1 和结束位置 right 压入栈中，等待下一轮排序。

3. 排序完成后，原序列就变成了有序的序列。

图示如下

在对0(begin)到9(end)进行一趟快排后，得到一个基准值key，如果左右两侧元素均不只有一个元素，将key左侧起始位置(begin)到key-1(end)位置压栈，再将key右侧keyi+1(begin)位置到右侧结束位置(end)压栈

代码实现：

我们使用如下的检测代码

 有

其实对于快速排序，我们可以发现它的整体是类似于完全二叉树的形式，而在数据量较少时，我们可以采取效率更高的插入排序，即