【手撕排序4】计数排序+快速排序(非递归)
> 🍃 本系列包括常见的各种排序算法，如果感兴趣，欢迎订阅🚩
> 🎊个人主页:[小编的个人主页])小编的个人主页
> 🎀 🎉欢迎大家点赞👍收藏⭐文章
> ✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍
🐼前言
🌟在上一节我们实现了归并排序，感受到了归并排序的魅力，如果感兴趣的小伙伴，可以阅读我的上一篇文章:>归并排序 这节小编主要分享计数排序和快速排序的非递归版本。
🐼计数排序
🔍计数排序是一种非比较排序，而在我们上述实现的所有排序中，都是比较排序。
其思想是，统计相同元素出现的次数；
根据 统计的结果将序列回收到原来的序列中 。
☀️动图解析:
👀 从上述动图，我们可以看出，需要创建一个计数的数组，那么这个数组需要开辟多大的空间呢?
从上面的案例看到，如果最大值是9，就开辟10个(最大值+1个)空间，因为下标是从0开始的。那如果是{100,101,102,103,104,105}.那需要开辟105+1个空间吗?显示，这会造成空间浪费。如图:
❄️如果我们能求出这组序列的最大值和最小值。那么就可以根据序列的范围(range = max-min+1)向操作系统申请空间，并将count数组中所有元素置为0，刚开始还没有计数。这样用于计数的数组就创建好了。
❄️这样，将原数组所有元素都映射到计数数组中，映射规则是:当前值-这组序列中的最小值。比如{100,101,102,103,104,105}序列。101映射到计数数组下标就是(101-100 = 1),所以在count数组下标为1的位置计数加1。以此类推，将原序列所有元素都映射到计数数组中，正如我们动图所演示。
👀那么想得到排序好的序列该咋办呢?
我们知道，count数组中每个位置下标所对应的值，就是映射过来的该元素对应出现的次数。
那么我们还原回去，就需要将count每个位置映射回去(原数组元素=计数数组下标+min),而我们又知道，count数组的值就是原数组出现次数,那计数几次，就映射几次过去。最后，不要忘记释放申请的count数组。
具体代码:
#include<string.h>
//计数排序(非比较排序)
void CountSort(int* arr, int n)
{
int min = arr[0], max = arr[0];
//找最大最小值
for (int i = 1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
int range = max - min +1;
//创建count数组,并初始化为0
//写法1
//int* count = (int*)calloc(sizeof(int)*range,sizeof(int));
//写法2
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL)
{
perror("malloc fail");
exit(-1);
}
memset(count, 0, sizeof(int) * range);
//计数
for (int i = 0; i < n; i++)
{
count[arr[i] - min]++;
}
//还原原数组
int index = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[index++] = i + min;
}
}
free(count);
count = NULL;
}🐼快速排序(非递归)
🔍在之前，我们实现了快速排序的三种实现方式，今天来完成快速排序的非递归版本。
在快速排序时，需要不断地根据基准值划分左右区间，就像二叉树一样。非递归的快速排序需要用栈来模拟划不断分左右区间这个过程，就像模拟二叉树的实现方式。
如图:
🍃我们用栈来模拟这个过程，先让原序列右下标和左下标入栈(先让右入栈，因为栈先入后出)，接着，只要栈不为空，就一次取两个元素，即左下标和右下标。再通过前面找基准值的三种方式，任意一种，找到keyi,此时划分左序列为[left,key-1],右序列[keyi+1,right],只要keyi + 1 < right,keyi-1>left,将右序列先入栈，再将左序列入栈。即入栈顺序:right->keyi+1->keyi-1->left.
具体代码
// 快速排序 非递归实现
void QuickSortNonR(int* arr, int left, int right)
{
ST st;
StackInit(&st);
StackPush(&st,right);
StackPush(&st, left);
while (!StackEmpty(&st))
{
//取栈顶两个元素
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
int prev = begin, cur = prev + 1;
int keyi = begin;
while (cur <= end)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
cur++;
}
Swap(&arr[prev], &arr[keyi]);
//基准值keyi
//左序列begin prev-1
//右序列prev+1 end
if (prev + 1 < end)
{
StackPush(&st, end);
StackPush(&st, prev + 1);
}
if (begin < prev - 1)
{
StackPush(&st, prev - 1);
StackPush(&st, begin);
}
}
STDestory(&st);
}🐼排序算法时间复杂度和稳定性
🔍稳定性:排序的稳定性是指在排序过程中，如果存在多个具有相同关键字的记录，这些记录在排序前后的相对顺序保持不变。这意味着在排序操作中，如果两个元素相同，它们在最终结果中的位置应与在原始数据集中的位置相同。
我们总结一下各种排序的性能对比:
感谢你看到这里，如果觉得本篇文章对你有帮助，点个赞👍 吧，你的点赞就是我更新的最大动力。⛅️🌈 ☀️
这车好有感觉~
原文地址：https://blog.csdn.net/2401_83251330/article/details/143606639
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！