快速排序是非常适合使用递归的,但是同时我们也要掌握非递归的算法
因为操作系统的栈空间很小,如果递归的深度太深,容易造成栈溢出
递归改非递归一般有两种改法:
- 改循环
- 借助栈(数据结构)
图示算法
不是递归,我们模拟递归的过程
代码示例
创建一个栈s,先入end,再入begin,先出左再出右
然后找这个区间的keyi,找到之后左区间就是[left,keyi-1],右区间就是[keyi+1,right]
如果区间不止一个值,那就继续入栈,单趟排序,入栈的顺序应与前面保持一致
stack
stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
int* 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;
pst->capacity = 0;
pst->top = 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, sizeof(STDataType) * newcapacity);
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);
/*if (pst->top == 0)
{
return true;
}
else
{
return false;
}*/
return pst->top == 0;
}
//栈的元素个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
QuickSortNonR
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
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;
}
}
int GetMidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2;
if (a[begin] < a[midi])
{
if (a[midi] < a[end])
return midi;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[midi] > a[end])
return midi;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}
//前后指针法
int PartSort3(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
//if (a[cur] < a[keyi])
//{
// ++prev;
// Swap(&a[prev], &a[cur]);
// ++cur;
//}
//else
// ++cur;
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
void QuickSortNonR(int* a, int begin, int end)
{
ST s;
STInit(&s);
STPush(&s, end);
STPush(&s, begin);
while (!STEmpty(&s))
{
int left = STTop(&s);
STPop(&s);
int right = STTop(&s);
STPop(&s);
int keyi = PartSort3(a, left, right);
if (left < keyi - 1)
{
STPush(&s, keyi - 1);
STPush(&s, left);
}
if (keyi + 1 < right)
{
STPush(&s, right);
STPush(&s, keyi + 1);
}
}
STDestroy(&s);
}
递归相当于把这些数据存到栈帧里边,而非递归是将核心区间存存到数据结构栈里面文章来源:https://www.toymoban.com/news/detail-758793.html
快速排序的特性总结
- 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
- 时间复杂度:O(N*logN)
- 空间复杂度:O(logN)
- 稳定性:不稳定
文章来源地址https://www.toymoban.com/news/detail-758793.html
到了这里,关于排序算法之六:快速排序(非递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!