文章图片
联系方式(qq)：623847465gitee(码云)：Mercury. (zzwlwp) - Gitee.com我一路种下了蘑菇，只是为了让你知道回家的路。 程序猿：我宁愿写bug，也不愿什么都不做！
上期学习完了前四个排序，这期我们来学习剩下的三个排序：
1、冒泡排序今天我们主要难点有快速排序和归并排序，会简单涉及到二叉树相关知识，相对来说比较抽象！所以如果有看不懂或者不明白的地方可以看看我之前的详解二叉树，也可以直接问我！教你打篮球的程序猿随时在线。
2、快速排序 ( 三种方法 )
3、归并排序
4、排序算法复杂度及稳定性分析
1、冒泡排序 冒泡排序是我们相对最好理解的个排序，但是有些小优化的地方我会指出来，我们先看图解：
文章图片
void BubbleSort(int* a, int n)//升序
{
//时间复杂度O(N^2)
while (n > 0)
{
int exchange = 0;
for (int i = 1;
i < n;
++i)//防止越界访问
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
//交换
exchange = 1;
}
}
if (exchange == 0)
{
break;
}
--n;
}
}代码分析：我们每排完一趟，就可以确定最后一个位置的数，再者我们定义了一个exchange来判断在排序过程中是否发生了交换，如果没有发生交换，证明此数组已经有序，我们可以直接跳出循环，避免不必要的循环！2、快速排序 ( 三种方法 )
冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2) 、空间复杂度：O(1)
3. 稳定性：稳定
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。第一种方法是我们最常见的挖坑法：
基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
文章图片
代码实现如下：
void QuickSort(int* a, int left, int right)//升序
{
if (left >= right)
{
return;
} int begin = left;
int end = right;
int pivot = begin;
int key = a[begin];
while (begin < end)
{
//右边找小
while (begin < end && a[end] >= key) //这里如果不写begin第二种方法左右指针法：
文章图片
代码实现如下：
void QuickSort(int* a, int left, int right)//升序
{
if (left >= right)
{
return;
} int begin = left;
int end = right;
int keyi = begin;
while (begin < end)
{
//找小
while (begin < end && a[end] >= a[keyi])
{
--end;
}
//找大
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
Swap(&a[begin], &a[end]);
} Swap(&a[begin], &a[keyi]);
keyi = begin;
//[left, keyi - 1] keyIndex [keyi + 1, right]
//左子区间和右子区间有序，我们就有序了，如何让他们有序呢？分治递归 QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}第三种方法前后指针法：
文章图片
代码实现如下：
void QuickSort(int* a, int left, int right)//升序
{
if (left >= right)
{
return;
} int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
//++prev != cur为了防止自己跟自己交换造成不必要的消耗
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
//[left, keyi - 1] keyi [keyi + 1, right]
//左子区间和右子区间有序，我们就有序了，如何让他们有序呢？分治递归 QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}3、归并排序
基本思想： 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 （Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
文章图片
归并排序我们思想还是和快排思想差不多采用分治算法，当数组被分为单独一个元素就是有序的了(见上图)，在接着归并到一个数组中，即可实现排序！
代码实现如下：
void _MergeSort(int* a, int left, int right, int* tmp)
{
if (left >= right)
return;
int mid = (left + right) >> 1;
// 假设[left, mid] [mid + 1, right] 有序，那么我们就可以归并了
_MergeSort(a, left, mid, tmp);
_MergeSort(a, mid + 1, right, tmp);
//归并
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] < a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
} while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
} while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
} //拷贝回去
for (int i = left;
i <= right;
++i)
{
a[i] = tmp[i];
}
}void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
}4、排序算法复杂度及稳定性分析
文章图片
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍 在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。I can do all things（我能做成任何事！）相信自己，加油！
文章图片
联系方式(qq)：623847465gitee(码云)：Mercury. (zzwlwp) - Gitee.com
【数据结构|常见的排序算法（下）】下期预告：待定
推荐阅读
- C语言|对比顺序表与链表——纵观与取舍
- C语言|十分钟手撕栈与队列——栈与队列实现详解
- 数据结构|反转链表-四种方法
- C语言提高（一）
- 笔记|嵌入式网络的基础知识
- Quant|量化分析师的Python日记【Q Quant兵器谱之函数插值】
- C语言|qsort库函数详解
- C语言|库函数《qsort》的模拟实现，原来如此简单
- c语言初学之路|【C语言】模拟实现库函数 strcpy(复制字符串内容) 与 strlen（求字符串长度）