数据结构——排序算法第二幕（交换排序：冒泡排序、快速排序（三种版本） 归并排序：归并排序（分治））超详细！！！！
文章目录
- 前言
- 一、交换排序
- 1.1 冒泡排序
- 1.2 快速排序
- 1.2.1 hoare版本 快排
- 1.2.2 挖坑法 快排
- 1.2.3 lomuto前后指针 快排
- 二、归并排序
- 总结
前言
继上篇学习了排序的前面两个部分:直接插入排序和选择排序
今天我们来学习排序中常用的交换排序以及非常稳定的归并排序
快排可是有多种方法的，高速列车，即将发车，fellow me
一、交换排序
交换排序基本思想：
所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
1.1 冒泡排序
冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。这个算法在平常算法题中基本不用(因为太慢了)，只能说具有教学意义。
就简单实现一下代码啦
void BubbleSort(int* a,int n)
{
int exchange = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j] > a[j + 1])
{
exchange = 1;
swap(a[j], a[i]);
}
}
if (!exchange)
break;
}
}
冒泡排序的特性总结
时间复杂度： O(N^2)
空间复杂度： O(1)
1.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序实现主框架：
其实快排主要就是递归，把一个大区间不断划分成子区间
void QuickSort(int* a, int left, int right)
{
if (left >= right)
{
return;
}
//_QuickSort用于按照基准值将区间[left,right)中的元素进行划分
int meet = _QuickSort(a, left, right);
QuickSort(a, left, meet - 1);
QuickSort(a, meet + 1, right);
}
1.2.1 hoare版本 快排
算法思路 ：
创建左右指针，确定基准值
从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环
其实就是确定一个数为基准值，然后根据基准值，把当前区域的数据分成两部分，左边小于基准值，右边大于基准值
然后再递归到分好的区域，继续重复操作，一个大问题划分成无数个一样的子问题。
讲到这里大概都知道怎么写啦，上代码
int _QuickSort(int* a, int left, int right)
{
int keyi = left; // 先定义区间第一个数为基准值
left++; // left++ 对除基准值以外的数据进行判断操作
while (left <= right) // 只要left<right 就继续循环
{ // 我们这里right是找比基准值小的数据 left是找比基准值大的数据 然后进行调换
while (left <= right && a[right] > a[keyi])// 当右边的值大于基准值时 right-- 直到找到小于基准值的再跳出循环
{
right--;
}
while (left <= right && a[left] < a[keyi])// 当左边的数据小于基准值时 left++ 直到找到大于基准值的再跳出循环
{
left--;
} // 两个循环跳出后 left对应的数据大于基准值 right对应的数据小于基准值
// 对数据进行调换 这样就把小的放在左边 大的放在右边
if (left <= right)
{
swap(a[right--], a[left++]);
}
} // 当left>right的时候 交换最开始的基准值的位置 这个时候新的基准值就取right
swap(a[right], a[keyi]);
return right; // 到此 新的区间划分就处理好了 新的基准值返回就好啦
}
第一个版本实现完毕了，可能会有些疑问
为什么跳出循环后right位置的值一定不大于key？
当left > right 时，即right走到left的左侧，而left扫描过的数据均不大于key，因此right此时指向的数据一定不大于key
可以试着自己模拟一下下面的流程图
问题2：为什么left 和 right指定的数据和key值相等时也要交换？
相等的值参与交换确实有一些额外消耗。实际还有各种复杂的场景，-假设数组中的数据大量重复时，相等也交换能进行有效的分割排序。
如果不相等才交换的话,假设数据全是相同的数据，那每次基准值只能找到初始基准值的下一个，时间复杂度会变成O(N^2)
快排是挺快的，但好东西总有缺陷
快排 ：hoare版本的时间复杂度
划分区间递归的时间复杂度为 logn
每次区间内找新的基准值时间复杂度为 n
时间复杂度为 N*logN
但是在数据有序的时候，时间复杂度还是O(N^2)，新的基准值只能找到key的下一个数字，划分区间的效率很低
1.2.2 挖坑法 快排
思路：
创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）。
就是先从右往左找，再从左往右找，不断循环，直到left>right,过程中数值一直在迭代交换，这个时候最后一个坑刚好放最开始挖的值。
相比hoare还是有差别的
int _QuickSort1(int* a, int left, int right)
{
int hole = left; // 找到第一个坑
int key = a[left]; // 把第一个坑保存起来
while (left < right) // left==right时跳出循环 最后一个坑
{
while (left < right && a[right] >= key) // 从右开始往左找
{
right--;
}
a[hole] = a[right]; // 当right--的循环跳出后 这个时候right对应的值小于key 把当前right的值换到坑里
hole = right; // right变成新的坑
while (left < right && a[left] <= key) // 从左开始往右找
{
left++;
}
a[hole] = a[left]; // 当left++的循环跳出后 这个时候left对应的值大于key 把当前left的值换到坑里
hole = left; // left变成新坑
}
a[hole] = key; // 大循环结束后 left=right
return hole; // 这个新坑留给一开始的key值 返回新的基准值下边
}
挖坑法完毕
挖坑法和hoare版本的时间复杂度一样 n*logn
但是在特殊情况也会有不好的地方 在数据有序的时候 时间复杂的还是会变成 O(N^2)
1.2.3 lomuto前后指针 快排
创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。
前后指针是我认为最好理解，也是代码最简单的一个
就是定义一个cur指针向前走，一个prev指针在后面跟着，cur找比基准值小的数据
话不多说，上代码
int _QuickSort1(int* a, int left, int right)
{
int prev = left; // 定义prev cur 指针
int key = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[key] && ++prev != cur) // 当cur对应的值小于key时，可以考虑将prev与cur对应的值交换
{ // 但如果这个时候，cur刚好是prev的下一个值，时没有必要交换的
swap(a[prev], a[cur]); // 所以要判断 prev++与cur是否相等
}
++cur; // 每次循环 cur++一次
}
swap(a[key], a[prev]); // 循环结束之后，prev对应的值时小于key的prev的下一个就是大于key的 这个时候调换key和prev的值
return prev; // 找到新的基准值下标返回
}
仔细了解前后指针的流程，想必也会感觉到，当数据有序或者是全部相同时
前后指针也是O(N^2)的时间复杂度，比起hoare和挖坑法 缺陷又多了一个数据全部相同时
想想数据全部相同或者有序，其实也没有排序的需要了，除非是算法题卡了数据相同的样例
所以快排的三种方法还是可行的
快速排序特性总结：
时间复杂度： O(nlogn)
空间复杂度： O(logn)
快排的基本内容就到这里啦
二、归并排序
归并排序算法思想：
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
底层核心还是递归，把一个大区间逐渐分成无数个小区间，（一个大问题分成无数个相同的子问题），快排和归并都是用到了递归，想想递归真的好用。
博客链接：合并两个有序数组
还有一个问题就是在递归到最后一层之后，怎么合并两个子区间让他们有序,这里我想到前面我们做过的习题，上面的链接供参考。
话不多说上代码
void _MergeSort(int* arr, int left, int right, int* tmp) // 把大区间分配数个小空间
{ // 两个小空间 排序成一个空间 用tmp接受 返回赋值给原数组
if (left >= right) // 递归出口
{
return;
}
int mid = left + (right - left) / 2;// 分成两个区间 采用二分
_MergeSort(arr, left, mid, tmp); // 左区间
_MergeSort(arr, mid + 1, right, tmp);// 右区间
// 递归处理之后 现在就是合并两个子区间 使他们有序
int begin1 = left, end1 = mid; // 第一个区间的begin和end
int begin2 = mid + 1, end2 = right; // 第二个区间的 begin和end
int index = begin1; // 新的下标 对应tmp数组
while (begin1 <= end1 && begin2 <= end2) // 合并两个数组的流程 不多赘述啦
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1) // 有数组没有全部传给tmp的情况
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
for (int i = left; i <= right; i++) // 赋值返回原数组
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n); // 我们这里传一个新开的tmp数组空间进去，辅助合并两个子区间
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}
仔细回看，归并其实也不难，就是一个递归的处理，然后再合并两个区间而已，洒洒水啦
实话实说，归并稳定，时间复杂度一直是O(nlogn) 不管数据是否有序是否相同 。
归并排序特性总结：
时间复杂度： O(nlogn)
空间复杂度： O(n)
总结
都说快排是个大家伙，现在学完来看，也就一般般嘛
回顾今天学习的内容，从快排的三种方式，到递归合并的归并排序
差不多都是围绕递归在展开排序，虽然快排有些许缺陷，但影响不大
现在想想，归并排序，又稳又好，就是代码有点多 哈哈哈哈
今天的学习就到这里啦，下一篇将深究一下快排以及非递归实现快排，不要走开，小编持续更新中~~~~
有差错的地方还请各位指出，小编必然马不停蹄来修改~~~~
