!
先赞后看,养成习惯!!!^ _ ^<3 ❤️ ❤️ ❤️
码字不易,大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦!
所属专栏:排序算法
思路如下:
一、先建立一个栈
为什么要建立栈呢?
建立栈是为了让每次排序的区间进去,然后后面便于取出
二、代码编写
这里用了之前的快速排序的一个格式(前后指针法)
注意事项:
1.每次判断key-1和key+1是否符合要求(keyi-1>left ,keyi+1<right)这样才能入栈
2.前后指针法排序时必须记住当cur走到right的时候,prev所在的位置一定小于或者等于key,此时出了循环一定要和left位置的值交换,这样可以使得key的位置已经排好了文章来源:https://www.toymoban.com/news/detail-843545.html
void Swap(int* p1, int* p2)
{
int tmp = *p2;
*p2 = *p1;
*p1 = tmp;
}
int QuickSort(int left,int right,int* a)
{
int prev = left;
int cur = left + 1;
int key = a[left];
while (cur <= right)
{
if (a[cur] <= key && ++prev != cur)
Swap(&a[cur],&a[prev]);
cur++;
}
Swap(&a[left], &a[prev]);
return prev;
}
void TestQuickSort(int begin,int end,int* a)
{
ST stack;
StackInit(&stack);
StackPush(&stack, end);
StackPush(&stack, begin);
while (!StackEmpty(&stack))
{
int left = StackTop(&stack);
StackPop(&stack);
int right = StackTop(&stack);
StackPop(&stack);
int keyi = QuickSort(left, right, a);
if (keyi + 1 < right)
{
StackPush(&stack, right);
StackPush(&stack, keyi + 1);
}
if (keyi - 1 > left)
{
StackPush(&stack, keyi - 1);
StackPush(&stack, left);
}
}
StackDestroy(&stack);
}
int main()
{
int a[10] = { 3,5,6,7,2,1,8,10,9,4 };
TestQuickSort(0,9,a);
for (int i = 0; i < 10; i++)
printf("%d ",a[i]);
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-843545.html
到了这里,关于排序算法:快速排序(非递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!