排序算法中——冒泡排序和快速排序
前言：上篇介绍了排序算法中的插入，选择，希尔和堆排序，本篇讲主要讲解冒泡排序和快速排序。
上篇链接：排序算法上——插入，希尔，选择，堆排序-CSDN博客
PS：本篇以排升序为例
一. 冒泡排序
动图分析：
冒泡排序在实际应用中作用并不大，因为他时间复杂度为O（n^2)，效率较低，但作为我们学到的
第一个排序方法，简单易懂，具有较大的教学意义。
- 总共n个数据，要排n-1趟
- 第i（i从0开始取）趟要比较n-1-i次
- 等差数列求和，最坏时间复杂度为O(n2)
- 定义exchange变量，当数组已经有序时不进入交换，直接跳出循环
- 最好时间复杂度为O(n)
- 空间复杂度O(1)
代码示例如下：
void BubbleSort(int* arr, int n)
{
for (int i = 0; i < n-1; i++)
{
int exchange = 0;
for (int j = 0; j < n - i - 1; j++)
{
//升序
if (arr[j] < arr[j + 1])
{
exchange = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (exchange == 0)
{
break;
}
}
}
优劣对比：
与直接插入排序法相比，比较次数一致，但冒泡排序的交换需要执行三次，而直接插入排序因为使用了tmp临时变量存储要插入的数据，只用执行一次，所以直接插入排序法效率明显更高。
与直接选择排序法相比，直接选择排序法无论数组是否有序都要执行到结束条件，不存在最好最坏时间复杂度。而冒泡排序因为使用了exchange变量进行优化，可以在最好时间复杂度上达到线性的结果。所以冒泡排序更胜一筹
二. 快速排序
2.1 含义及主要思想框架
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法。
其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列 在相应位置上为⽌。
2.2 递归法实现
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//[left,right]--->找基准值mid
int keyi = _QuickSort(arr, left, right);
//左子序列：[left,keyi-1]
QuickSort(arr, left, keyi - 1);
//右子序列：[keyi+1,right]
QuickSort(arr, keyi + 1, right);
}
快速排序的核心在于找基准值！！！
以基准值为分界线，左侧区间全部小于基准值，右侧区间全部大于基准值，之后左右区间逐步递归
完成排序。
2.3 几种实现方法
hoare排序
主要思想：
假设将序列第一个数作为基准值
定义左右指针
- left：从左找比基准值大的 ，right：从右找比基准值小的
- 找到后交换，left++，right–，进入下次循环
跳出循环后交换基准值到正确位置
代码示例如下：
int _QuickSort1(int* arr, int left, int right)
{
int keyi = left;
++left;
while (left <= right)//left和right相遇的位置的值比基准值要大
{
while (left <= right && arr[right] > arr[keyi])
{·
right--;
}
//right找到比基准值小/ 等于？
while (left <= right && arr[left] < arr[keyi])
{
left++;
}
//right left
if (left <= right)
{
Swap(&arr[left++], &arr[right--]);
}
}
//right keyi交换
Swap(&arr[keyi], &arr[right]);
return right;
}
分析：
此处应注意，我们传入的left和right是所需排序区间的下标！因此在判断条件处需要取等于，否则无法排序完全。
跳出外层循环应该与right处数据交换，right处数据就是基准值的位置
问题：假设数组全是相同的数据呢？
分析：
- 取等于，第一次循环right就和left都在下标为1的位置，此时返回去的基准值就是下标1，左序列只有一个数据，右边序列还有n-2个数据
- 同样的下次循环的左序列也只有一个数据
- 像这样一次排一个数据时间复杂度很高
所以不应该取等于，尽量让左右子序列的数据个数平均一些。
挖坑法
动图理解：
主要思路：
1. 首先将left处设为坑位，值设为key，之后R向右遍历，寻找小于key的值。
2. 当R找到时，将此时的位置设为坑位，并将该值放入原先的坑位。
3. 此时L开始向右遍历，寻找大于key的值。
4. 当L找到时，将此时的位置设为坑位，并将该值放入原先的坑位。
5.重复操作直到L与R相遇，并将相遇的值与key替换。
代码示例如下：
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
while (left < right && arr[right] > key)
{
--right;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] < key)
{
++left;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
注意：
在该循环中，每次都是R先移动，因此最后相遇时位置的值必定小于key，所以直接交换即可。
前后指针
动图理解：
这个思路动图已经展现的很明确了，因此不做过多阐述。由于prev每次停留的位置的值都小于key，因此当cur遍历完全时，直接交换即可。
代码示例如下：
//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{
int prev = left, cur = left + 1;
int keyi = left;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}
递归法复杂度分析：
时间复杂度：每一层的总时间复杂度都是O（n），因为需要对每一个元素遍历一次。而且在最好的情况下，同样也是有logn层，所以快速排序最好的时间复杂度为O（nlogn）。
空间复杂度：二叉树递归最大深度为logn，即O（nlogn）
以上是最好情况，最坏情况则是上面说的一次排序一个数据，时间复杂度O(n2)，空间复杂度O(n)。不过现实中基本不会出现这种情况。
2.4 非递归法实现
- 栈是先进后出，所以插入先插入right后插入left
- 找基准值方法使用双指针法最简单
- 根据基准值划分左右区间
- 左区间：[begin,keyi-1]
- 右区间：[keyi+1,end]
- 循环直到栈为空
代码示例如下：
//非递归版本快排
//--借助数据结构--栈
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
STInit(&st);
StackPush(&st, right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶元素---取两次
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//[begin,end]---找基准值
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//根据基准值划分左右区间
//左区间：[begin,keyi-1]
//右区间：[keyi+1,end]
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
STDestroy(&st);
}
小结：以上就是冒泡排序和快速排序方法的介绍啦，欢迎各位佬前来支持斧正！！！
