数据结构排序算法详解（3）——交换排序（附动图）
前言
嗨٩(๑❛ᴗ❛๑)۶，前两篇讲解了插入排序和选择排序两种，今天我们继续来了解排序，本篇来讲几种交换排序——冒泡排序和快速排序，让我们来了解他们吧！
五、交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
1、冒泡排序
（1）概念及实现
概念：重复遍历待排序数组，每一轮依次比较相邻的两个元素，若顺序错误（如升序排序时前大后小）则交换它们；每完成一轮遍历，当前未排序部分的最大元素会被 “冒泡” 到末尾；重复此过程直到整个数组有序 这是我们的老朋友了，可是还有很多人不理解冒泡排序是怎么进行的？博主这里用动图来帮助大家更好的理解
请添加图片描述
我们这里直接实现
// O(N^2) 最坏
// O(N) 最好
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
// 单趟
int flag = 0;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}测试：
int main()
{
int arr[] = { 2,5,3,76,9,10,32,11,2 };
PrintArray(arr, sizeof(arr) / sizeof(int));
BubbleSort(arr, sizeof(arr) / sizeof(int));
PrintArray(arr, sizeof(arr) / sizeof(int));
/*TestOP();*/
return 0;
}结果升序，符合
在这里插入图片描述
（2）时间复杂度
- O(n2) 最好是全部有序，只用遍历一遍，时间复杂度为O(n) 但概率太小，通常不是有序 所以时间复杂度为O(n2)
（3）特性
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
2、快速排序
（1）快速排序的由来及思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法， 其基本思想为： 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 这里有很多版本，我们依次来讲
（2）hoare版本（递归）
思想： 1、创建左右指针，确定基准值 2、从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环 我们可以通过动图来观察
请添加图片描述
就是保证l前面都比key小，r后面都比key大，相遇时一定比key小，再把相遇对应元素与key交换，拆分为2个数组 【l的起始位置，相遇-1】【相遇+1，r的起始位置】 再进行排序
实现（原版）
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
//左边做key，先让右边先走，再让左边走(可以保持key比停下的位置的元素大)
//右边做key，先让左边先走，再让右边走(可以保持key比停下的位置的元素小)
//结论：一边做key，让另一边先走
while (begin < end && arr[end] >= arr[keyi])
{
end--;
}
while (begin < end && arr[begin] <= arr[keyi])
{
begin++;
}
Swap(&arr[begin], &arr[end]);
}
Swap(&arr[keyi], &arr[begin]);
keyi = begin;
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}我们发现当数组已完全升序或完全逆序时，且我们选择的基准值（keyi = left，即区间最左侧元素）恰好是当前区间的最小值（升序）或最大值（逆序），此时会导致快速排序的分治策略失效，退化为类似冒泡排序的低效情况。 导致这种
在这里插入图片描述
（3）hoare优化
三数取中法
我们如果要解决这个问题就需要让key所在位置的值是折中的，不能太大也不能太小，所以就想到了三数取中这个方法： 我们通过比较开头，中间，结尾3个数取中间大的那个数与开头key交换 代码如下:
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
// left midi right
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
return;
int midi = GetMidi(arr,left,right);
Swap(&arr[left], &arr[midi]);
int keyi=left;
int begin = left, end = right;
while (begin < end)
{
//左边做key，先让右边先走，再让左边走(可以保持key比停下的位置的元素大)
//右边做key，先让左边先走，再让右边走(可以保持key比停下的位置的元素小)
//结论：一边做key，让另一边先走
while (begin < end && arr[end] >= arr[keyi])
{
end--;
}
while (begin < end && arr[begin] <= arr[keyi])
{
begin++;
}
Swap(&arr[begin], &arr[end]);
}
Swap(&arr[keyi], &arr[begin]);
keyi = begin;
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}通过这个方法我们可以解决keyi的影响，那么还可以再优化优化吗？当然可以
小区间优化
我们通过代码及分析可看出来快速排序的逻辑就是基于二叉树递归的逻辑实现的，我们联想一下
在这里插入图片描述
递归过程是这样的，但是当区间缩小到小区间（如长度≤10~15）时，排序本身的计算量（比较、交换次数）极少，但递归开销的占比会显著升高 ，我们通过我们对二叉树的了解，最后一次递归占总递归的50%，倒数第二层占25%。 所以我们通过当剩余元素小于一定值时，采用插入排序（其他排序也行）
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
InsertSort(a+left, right - left + 1);
}
else
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
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[keyi], &a[begin]);
keyi = begin;
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}（4）hoare总和(优化后）
//三数取中法
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
// left midi right
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
// 避免有序情况下，效率退化
// 1、随机选key
// 2、三数取中
// 后续讲一下思路即可
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
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[keyi], &a[begin]);
keyi = begin;
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}（5）Hoare前后指针版本快排
在基于hoare思想下，有人提出了前后指针版本
- 思路：创建前后指针，从左到右找比基准值小的进行排序，是小的都排在基准值左边，
- 过程： 1、创建左右指针prev和cur,cur从左往右找比基准值要小的数据 2、cur指向的数据比基准值要小的话，++prey,换cur和prev位置的值，再++cur 3、cur信向的数据不比基准值小的话，直接++cur.循环结束后，交换keyi位置和prev位置的值，返回prev下标 图示
请添加图片描述
代码实现： 这个方法只是对快速排序的单趟进行了修改，多趟还是基于二叉树的递归思想解决的，递归方法还是一样，也可以通过三数取中法和小区间优化，这里只改变else中的内容即可
//lomuto前后指针实现快排
void QuickSort2(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
if ((right - left + 1) < 10)
{
InsertSort(arr + left, right - left + 1);
}
else
{
int midi = GetMid(arr, left, right); //三数取中
Swap(&arr[left], &arr[midi]);//将中间值与开头进行交换来作为key
int keyi = left;
//lomuto前后指针(单趟)
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (arr[cur] < arr[keyi])
{
prev++;
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
//与二叉树的递归逻辑相同：[left, keyi - 1] keyi [keyi + 1, right]
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
}（5）挖坑法快速排序
有人觉得传统左右指针法和horea法考虑的太多，不直观，就出现了这种方法 概念: 快速排序的挖坑法是快速排序的一种实现方式，核心逻辑是通过 “挖坑→填坑→更新坑位” 的方式确定基准值的最终位置，相比传统左右指针法，逻辑更直观，避免了指针交换时的边界问题。 过程：
在这里插入图片描述
动图展示：
请添加图片描述
代码实现：
// 快速排序（挖坑法+三数取中+小区间优化）
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小区间优化：长度<10时用插入排序
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
// 三数取中优化：选中位数作为基准，交换到left位置
int midIdx = GetMidi(a, left, right);
Swap(&a[left], &a[midIdx]); // 将中位数换到left，作为基准
int key = a[left]; // 基准值
int pit = left; // 初始坑位
while (left < right)
{
// 右指针找比key小的元素，填左坑
while (left < right && a[right] >= key)
{
--right;
}
a[pit] = a[right];
pit = right; // 更新坑位
// 左指针找比key大的元素，填右坑
while (left < right && a[left] <= key)
{
++left;
}
a[pit] = a[left];
pit = left; // 更新坑位
}
a[pit] = key; // 基准值填入最终坑位
int keyi = pit; // 定义keyi并赋值为基准位置pit
QuickSort(a, left, keyi - 1); // 递归左区间
QuickSort(a, keyi + 1, right); // 递归右区间
}
}（6）封装三类快速排序
我们发现hoare排序、双指针排序、挖坑法排序这三种只是在else中不同，分治递归的步骤都一样，所以我们把他们进行封装 PartSort1——hoare排序 PartSort2——双指针排序 PartSort3——挖坑排序
//三数取中法
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
// left midi right
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
//hoare快排
int PartSort1(int* a, int left, int right)
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
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[keyi], &a[begin]);
return begin;
}
//lomuto前后指针实现快排
int PartSort2(int* a, int left, int right)
{
int midi = GetMidi(a, left, right); //三数取中
Swap(&a[left], &a[midi]);//将中间值与开头进行交换来作为key
int keyi = left;
//lomuto前后指针(单趟)
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi]&&++prev!=cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
// 挖坑法单趟排序（结合三数取中）
int PartSort3(int* a, int left, int right)
{
// 三数取中优化：选中位数作为基准，交换到left位置
int midIdx = GetMidi(a, left, right);
Swap(&a[left], &a[midIdx]); // 将中位数换到left，作为基准
int key = a[left]; // 基准值
int pit = left; // 初始坑位
while (left < right)
{
// 右指针找比key小的元素，填左坑
while (left < right && a[right] >= key)
{
--right;
}
a[pit] = a[right];
pit = right; // 更新坑位
// 左指针找比key大的元素，填右坑
while (left < right && a[left] <= key)
{
++left;
}
a[pit] = a[left];
pit = left; // 更新坑位
}
a[pit] = key; // 基准值填入最终坑位
return pit; // 返回基准位置
}
// 避免有序情况下，效率退化
// 1、随机选key
// 2、三数取中
// 后续讲一下思路即可
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
int keyi = PartSort1(a, left, right);
/*int keyi = PartSort2(a, left, right);
int keyi = PartSort3(a, left, right);*/
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}在这里统一验证 这三个依次验证
在这里插入图片描述
结果都正确
在这里插入图片描述
（7）时间复杂度
这三种排序时间复杂度都为O(n*logn) 因为都递归方法都一致，深度都为logn,每一层还为n个元素 因为我们使用了三数取中，让基准值尽可能接近区间中位数，使每轮划分都能将数组均匀分割，递归深度稳定为logn层；每轮划分需遍历 n个元素
总时间复杂度仍为O(n*logn)
（8）快速排序的特性
1.快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 2.时间复杂度：O(N*1ogN) 3.空间复杂度：O(logN)
在这里插入图片描述
3、对比插入排序、选择排序和交换排序
对比代码还是这个，创造10万个数看看，这里快速排序时间复杂度都一样，所以我们随便选择一个
#include"Sort.h"
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
// Öظ´²»¶à
a1[i] = rand() + i;
// Öظ´½Ï¶à
//a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
//PrintArray(a2, N);
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
//MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
BubbleSort(a7, N);
int end7 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
//printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
/* int arr[] = { 2,5,3,76,9,10,32,11,2 };
PrintArray(arr, sizeof(arr) / sizeof(int));
QuickSort(arr, 0,sizeof(arr) / sizeof(int)-1);
PrintArray(arr, sizeof(arr) / sizeof(int));*/
TestOP();
return 0;
}结果
在这里插入图片描述
我们可以看出冒泡排序十分慢，希尔、堆排序、快排、都是十分快的
4、补充——用栈或队列实现快速排序（非递归版本）
我们在学习快速排序这几种（递归实现）排序时，我们会有一种疑惑——递归是需要开辟栈空间的，但栈空间是非常有限的，当递归深度太深时，会出现栈溢出的风险，所以我们来利用非递归来实现快排
（1）使用栈来实现快速排序
我们非递归实现快速排序需要借助数据结构——栈 数据结构中栈是通过在堆区开辟空间，而堆区的空间是远大于栈的，也不会出现溢出的风险 我们怎么用栈来模拟递归排序呢？ 其实十分简单，就是用栈存储需要查找的左右边界，查找时再取出，进行一次排序遍历（我们前面封装排序就是封装单次排序），得到一个基点key，左边比他小，右边比他大，在把【left,key-1】【key+1,end】四个值存入栈，而栈的特点是先进后出。所以我们先存右边界，再存储左边界 具体过程如图：
在这里插入图片描述
代码实现： 我们前面数据结构专栏中已经实现栈的功能
在这里插入图片描述
将栈的代码粘贴到文件夹中，再点击添加
在这里插入图片描述
栈的代码这里有 栈与队列核心篇（上）：从原理到代码，吃透栈结构 再在Sort.c加include"Stack.h" 现在来实现啦
// 用栈模拟系统递归栈，实现快速排序的非递归版本
// a: 待排序数组，left: 区间左边界，right: 区间右边界
void QuickSortNonR(int* a, int left, int right)
{
ST st; // 定义栈结构（存储待排序区间的左右边界）
STInit(&st); // 初始化栈
STPush(&st, right); // 先压入右边界（栈是后进先出，需按“左、右”顺序弹出，故先压右、再压左）
STPush(&st, left); // 再压入左边界，栈中此时存储的是初始区间[left, right]
// 栈非空时循环处理区间
while (!STEmpty(&st))
{
// 弹出当前区间的左边界begin
int begin = STTop(&st);
STPop(&st);
// 弹出当前区间的右边界end
int end = STTop(&st);
STPop(&st);
// 小区间优化：长度<10时用插入排序，跳过后续分治
if (end - begin + 1 < 10)
{
InsertSort(a + begin, end - begin + 1); // a+begin指向区间起始位置
continue; // 跳过后面的PartSort和入栈，处理下一个栈内区间
}
// 执行单趟排序（PartSort2为自定义单趟排序函数，如Hoare法/挖坑法），返回基准位置keyi
int keyi = PartSort2(a, begin, end);
// 划分后的区间：[begin, keyi-1] （基准左）、keyi（基准）、[keyi+1, end]（基准右）
// 若右子区间有效（长度>1），将其边界压入栈（先压右、再压左）
if (keyi + 1 < end)
{
STPush(&st, end); // 压入右子区间的右边界
STPush(&st, keyi + 1); // 压入右子区间的左边界
}
// 若左子区间有效（长度>1），将其边界压入栈（先压右、再压左）
if (begin < keyi - 1)
{
STPush(&st, keyi - 1); // 压入左子区间的右边界
STPush(&st, begin); // 压入左子区间的左边界
}
}
STDestroy(&st); // 释放栈资源，避免内存泄漏
}其中单趟排序用哪个都行，博主感觉PartSort2双指针挺好，这里使用了双指针单次遍历，用其他的也可以
（2）用队列实现快速排序
因为队列的特点是先入先出，所以这里只是改变一下存储·顺序就行啦，但是这就变成了层序遍历，前面操作还是一样，这里就不做演示啦 相关代码实现前面已经实现： 栈与队列核心篇（下）：从基础到进阶，玩转队列设计
在这里插入图片描述
#include"Queue.h"
// 用队列实现快速排序（非递归）
void QuickSortNonR2(int* a, int left, int right)
{
Queue qe;
QueueInit(&qe);
QueuePush(&qe, left);//先进先出先加左边
QueuePush(&qe, right);
while (!QueueEmpty(&qe))
{
int begin = QueueFront(&qe);
QueuePop(&qe);
int end = QueueFront(&qe);
QueuePop(&qe);
// 小区间优化：长度<10时用插入排序，跳过后续分治
if (end - begin + 1 < 10)
{
InsertSort(a + begin, end - begin + 1); // a+begin指向区间起始位置
continue; // 跳过后面的PartSort和入栈，处理下一个栈内区间
}
int key = PartSort1(a, begin, end);
if (key - 1 > begin)//如果左存在先压左
{
QueuePush(&qe, begin);
QueuePush(&qe, key - 1);
}
if (key + 1 < end)//如果右存在先压右
{
QueuePush(&qe, key + 1);
QueuePush(&qe, end);
}
}
QueueDestroy(&qe);
}（3）时间复杂度
还是O(n*logn),因为这两种方法只是将递归转换成了循环，时间复杂度不变
5、总代码
栈的实现代码
Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);
// 入栈 出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
// 取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
// 初始化和销毁
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
// top指向栈顶数据的下一个位置
pst->top = 0;
// top指向栈顶数据
//pst->top = -1;
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
// 入栈 出栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
// 扩容
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;
pst->capacity = newcapacity;
}
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
// 取栈顶数据
STDataType STTop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
// 获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}队列的实现代码
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);
// 取队头和队尾的数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
//// 队尾插入
//void QueuePush(QNode** pphead, QNode** pptail, QDataType x);
//// 队头删除
//void QueuePop(QNode** pphead, QNode** pptail);Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->next = NULL;
newnode->val = x;
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
// 队头删除
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
/*QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
if (pq->phead == NULL)
pq->ptail = NULL;*/
// 一个节点
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else // 多个节点
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}排序总代码
Sort.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
//直接插入排序
void InsertSort(int* a, int n);
// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n);
//打印
void PrintArray(int* a, int n);
//交换
void Swap(int* p1, int* p2);
//直接选择排序
void SelectSort(int* a, int n);
//堆排序
void HeapSort(int* a, int n);
//向下调整建堆
void AdjustDown(int* a, int n, int parent);
//冒泡排序
void BubbleSort(int* a, int n);
//快速排序
void QuickSort(int* arr, int left, int right);
//三数取中法
int GetMidi(int* a, int left, int right);
//hoare快排
int PartSort1(int* a, int left, int right);
//lomuto前后指针实现快排
int PartSort2(int* a, int left, int right);
// 挖坑法单趟排序（结合三数取中）
int PartSort3(int* a, int left, int right);
//用栈模拟快速排序
void QuickSortNonR(int* a, int left, int right);
// 用队列实现快速排序（非递归）
void QuickSortNonR2(int* a, int left, int right);Sort.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
//直接插入排序
void InsertSort(int* a, int n)
{
// [0, n-1]
for (int i = 0; i < n - 1; i++)
{
// [0, n-2]是最后一组
// [0,end]有序 end+1位置的值插入[0,end]，保持有序
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
//升序大于>,降序小于
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
// O(N ^ 1.3)
//希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
// +1保证最后一个gap一定是1
// gap > 1时是预排序
// gap == 1时是插入排序
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
//打印
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; ++i)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
if (begin == maxi)
maxi = mini;
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}
//向下调整建堆
void AdjustDown(int* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // child >= n说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆排序
void HeapSort(int* a, int n)
{
// 向下调整建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
// O(N^2) 最坏
// O(N) 最好
//冒泡排序
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
// 单趟
int flag = 0;
for (int i = 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}
//三数取中法
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
// left midi right
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
//hoare快排
int PartSort1(int* a, int left, int right)
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
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[keyi], &a[begin]);
return begin;
}
//lomuto前后指针实现快排
int PartSort2(int* a, int left, int right)
{
int midi = GetMidi(a, left, right); //三数取中
Swap(&a[left], &a[midi]);//将中间值与开头进行交换来作为key
int keyi = left;
//lomuto前后指针(单趟)
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi]&&++prev!=cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
// 挖坑法单趟排序（结合三数取中）
int PartSort3(int* a, int left, int right)
{
// 三数取中优化：选中位数作为基准，交换到left位置
int midIdx = GetMidi(a, left, right);
Swap(&a[left], &a[midIdx]); // 将中位数换到left，作为基准
int key = a[left]; // 基准值
int pit = left; // 初始坑位
while (left < right)
{
// 右指针找比key小的元素，填左坑
while (left < right && a[right] >= key)
{
--right;
}
a[pit] = a[right];
pit = right; // 更新坑位
// 左指针找比key大的元素，填右坑
while (left < right && a[left] <= key)
{
++left;
}
a[pit] = a[left];
pit = left; // 更新坑位
}
a[pit] = key; // 基准值填入最终坑位
return pit; // 返回基准位置
}
// 避免有序情况下，效率退化
// 1、随机选key
// 2、三数取中
// 后续讲一下思路即可
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 小区间优化，不再递归分割排序，减少递归的次数
if ((right - left + 1) < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
//int keyi = PartSort1(a, left, right);
int keyi = PartSort2(a, left, right);
// int keyi = PartSort3(a, left, right);
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
}
#include"Stack.h"
//用栈模拟快速排序
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
// 小区间优化：长度<10时用插入排序，跳过后续分治
if (end - begin + 1 < 10)
{
InsertSort(a + begin, end - begin + 1); // a+begin指向区间起始位置
continue; // 跳过后面的PartSort和入栈，处理下一个栈内区间
}
int keyi = PartSort2(a, begin, end);
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
#include"Queue.h"
// 用队列实现快速排序（非递归）
void QuickSortNonR2(int* a, int left, int right)
{
Queue qe;
QueueInit(&qe);
QueuePush(&qe, left);//先进先出先加左边
QueuePush(&qe, right);
while (!QueueEmpty(&qe))
{
int begin = QueueFront(&qe);
QueuePop(&qe);
int end = QueueFront(&qe);
QueuePop(&qe);
// 小区间优化：长度<10时用插入排序，跳过后续分治
if (end - begin + 1 < 10)
{
InsertSort(a + begin, end - begin + 1); // a+begin指向区间起始位置
continue; // 跳过后面的PartSort和入栈，处理下一个栈内区间
}
int key = PartSort1(a, begin, end);
if (key - 1 > begin)//如果左存在先压左
{
QueuePush(&qe, begin);
QueuePush(&qe, key - 1);
}
if (key + 1 < end)//如果右存在先压右
{
QueuePush(&qe, key + 1);
QueuePush(&qe, end);
}
}
QueueDestroy(&qe);
}test.c
#include"Sort.h"
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);/*
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);*/
for (int i = 0; i < N; ++i)
{
// Öظ´²»¶à
a1[i] = rand() + i;
// Öظ´½Ï¶à
//a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
/*a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];*/
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
//PrintArray(a2, N);
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
//QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
//MergeSort(a6, N);
int end6 = clock();
int begin7 = clock();
//BubbleSort(a7, N);
int end7 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
/*printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
printf("BubbleSort:%d\n", end7 - begin7);*/
free(a1);
free(a2);
free(a3);
free(a4);
/*free(a5);
free(a6);
free(a7);*/
}
int main()
{
int arr[] = { 2,5,3,76,9,10,32,11,2 };
PrintArray(arr, sizeof(arr) / sizeof(int));
QuickSort(arr, 0,sizeof(arr) / sizeof(int)-1);
PrintArray(arr, sizeof(arr) / sizeof(int));
/*TestOP();*/
return 0;
}结束语
嗨！(^_−)☆本篇到这里就结束啦！本篇将交换排序进行讲解，主要讲了快速排序的几种版本及非递归版本。最重要的还是快速排序，我们就剩一个归并排序啦！就让下一篇进行讲解吧！让我们敬请期待吧！ 希望大家都会有所收获！感谢大家的支持啦！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-11-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号