排序算法之六：快速排序（非递归）

快速排序是非常适合使用递归的，但是同时我们也要掌握非递归的算法

因为操作系统的栈空间很小，如果递归的深度太深，容易造成栈溢出

递归改非递归一般有两种改法：

1. 改循环
2. 借助栈（数据结构）

图示算法 

 

不是递归，我们模拟递归的过程

代码示例

创建一个栈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--;}elsebreak;}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;elsereturn end;}else{if (a[midi] > a[end])return midi;else if (a[end] > a[begin])return begin;elsereturn 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);
}

递归相当于把这些数据存到栈帧里边，而非递归是将核心区间存存到数据结构栈里面

快速排序的特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定