C语言 | 栈的应用 | 非递归栈实现快排
2023-09-27 14:28:32 时间
/* 非递归栈实现快排 */
#include <stdio.h>
#include <math.h>>
#include <malloc.h>
#include <windows.h>
typedef struct _Stack
{
int *data;
int top;
}Stack;
/* 一次快排的结果,返回基准的位置 */
int OneQuickSort(int *arr, int i, int j)
{
//②if(j - i < 1) return -1;
int tmp = arr[i]; //基准
while( i < j )
{
while( i < j )
{
if(arr[j] < tmp) break;
j--;
}
arr[i] = arr[j]; //向前移动
while(i < j)
{
if(arr[i] > tmp) break;
i++;
}
arr[j] = arr[i]; //向后移动
}
arr[i] = tmp; //j == i
return i;
}
void QuickSort(int *arr, int left, int right)
{
Stack st;
//栈的长度最长不超过 log2(n)
int size = (int)log10(right-left+1)/log10(2.0);
size = (size+1)*sizeof(int);
st.data = (int*)malloc(size);
st.top = 0;
//入栈
st.data[st.top++] = left;
st.data[st.top++] = right;
//循环模拟递归
while(st.top != 0)
{
/* 出栈 快排 */
right = st.data[--st.top];
left = st.data[--st.top];
int mod = OneQuickSort(arr, left, right);
//与基准的紧挨着,为有序状态
if(mod - left > 1) //②if(mid != -1)
{
st.data[st.top++] = left;
st.data[st.top++] = mod - 1;
}
if(right - mod > 1)
{
st.data[st.top++] = mod + 1;
st.data[st.top++] = right;
}
}
free(st.data);
}
测试
int main()
{
int arr[] = {1,54,6,6,748,768,7,64,6379,76,78,746,7,64};
QuickSort(arr, 0, sizeof(arr)/sizeof(arr[0]) - 1);
int len = sizeof(arr)/sizeof(arr[0]);
for(int i = 0; i < len; i++)
{
printf("%d ",arr[i]);
}
system("pause");
return 0;
}
截图:
相关文章
- 【C语言】结构体进阶详解
- 【短道速滑七】使用SIMD指令加速大数据的CRC32值的计算,可较普通C语言提高8倍速度。
- C语言中字符串结束符'0'
- linux下的C语言开发 进程创建 延伸的几个例子
- C语言-排序和查找
- C语言open()函数:打开文件函数(转)
- C语言:计算一个数是否可为两个素数之和
- 03【C语言 & 趣味算法】(值得品味的一道题)打鱼还是晒网?结构体的简单应用。函数的应用。判断闰年的应用。求指定日期距1990年1月1日的天数。
- 【*** C语言 数组与static 应用 编程实例(值得思考 附static总结)——习题8.1(2)(苏小红版C语言(第3版))】
- 【C语言】飞机大战游戏还原,源码在文末,应用“循环”与“数组”实现游戏开发,一起玩一下经典小游戏吧
- 2021-03 青少年软件编程(C语言)等级考试试卷(五级)解析
- C语言------数据类型与输入输出
- C语言之基本算法24—黄金切割法求方程近似根
- C语言程序设计基础|部分和问题
- 李洪强漫谈iOS开发[C语言-024]-表达式与赋值运算符
- C语言版flappy bird黑白框游戏