快速排序的非递归实现：借助栈实现、借助队列实现

目录

用栈实现快速排序

1.用栈实现非递归快速排序的思路步骤

1.1.思路步骤

2.用栈实现非递归快速排序的代码

3.用栈实现非递归快速排序的整个工程

3.1.QuickSortNonR.h

3.2.QuickSortNonR.c

3.3.Stack.h

3.4.Stack.c

用队列实现非递归快速排序

1.用队列实现非递归快速排序的思路步骤

1.1.思路步骤

1.2.总结

2.用队列实现非递归快速排序的代码

3.用队列实现非递归快速排序的整个工程

3.1.QuickSortNonR.h

3.2.QuickSortNonR.c

3.3.Queue.h

3.4.Queue.c

总结

用栈实现非递归快速排序：

用队列实现非递归快速排序：

---

用栈实现快速排序

1.用栈实现非递归快速排序的思路步骤

图形解析：

非递归快速排序是通过模拟递归快速排序调用栈帧的行为去实现的。而递归快速排序思路是通过在内存栈上不断建立函数栈帧并利用新创建的函数栈帧来存放每个子区间的下标从而实现递归的快速排序，所以非递归快速排序实则是借助栈来手动模拟这个过程。

以下是快速排序非递归实现如何借助栈来模拟递归快速排序调用栈帧的行为，从而实现非递归快速排序的思路步骤的详细说明：

1.1.思路步骤

• 初始化：

  • 检查传入的数组区间是否有效。如果 begin >= end，则无需排序，直接返回。
  • 创建一个栈 st，用于存储子区间的起始和结束下标。
  • 初始化栈 st。

• 入栈初始区间：

  • 将待排序数组的初始区间 [begin, end] 的起始和结束下标压入栈 st 中。这模拟了递归快速排序中第一次函数调用时的行为。

• 模拟递归调用栈帧：

  • 当栈 st 不为空时，进入一个循环，模拟递归调用栈帧的行为。

• 区间出栈：

  • 从栈 st 中弹出当前区间的结束下标 end 和起始下标 begin。由于栈是后进先出的，所以先弹出的是 end，然后是 begin。

• 单趟排序：

  • 对当前区间 [begin, end] 进行单趟排序，找到基准值 key 的正确位置 keyi。这个过程模拟了递归函数中对子区间的处理。

• 确定左右子区间：

  • 根据基准值的位置 keyi，将当前区间划分为左右两个子区间 [begin1, end1] 和 [begin2, end2]。

• 子区间入栈：

  • 如果右子区间 [begin2, end2] 包含多于一个元素，则将其起始和结束下标先压入栈 st 中。这模拟了递归中对右子区间的函数调用。
  • 如果左子区间 [begin1, end1] 包含多于一个元素，则将其起始和结束下标压入栈 st 中。这模拟了递归中对左子区间的函数调用。
  • 通过先压入右子区间再压入左子区间，我们确保了在后续的循环中会先处理左子区间，这符合递归快速排序的前序遍历顺序。

• 重复处理：

  • 回到步骤4，继续处理栈中的下一个区间，直到栈为空。

• 结束：

  • 当栈 st 为空时，所有子区间都已排序完毕，非递归快速排序结束。

• 销毁栈：

  • 最后，销毁栈 st，释放其占用的内存资源。

通过以上步骤，非递归快速排序利用自定义栈 st 模拟了递归快速排序中的函数调用栈帧行为，包括子区间的划分和函数调用顺序。这样，我们就可以在不使用递归的情况下，通过迭代的方式实现快速排序。

2.用栈实现非递归快速排序的代码

//非递归的快速排序->利用栈模拟递归版本快速排序思路(即模拟二叉树的前序遍历思路)
void QuickSortNonR(int* a, int begin, int end)//NonR->注释：非递归的缩写
{if (begin >= end)return;//1.创建栈stST st;//2.堆栈st进行初始化StackInit(&st);//3.当前区间[begin，end]进栈stStackPush(&st, begin);StackPush(&st, end);//4.若栈不为空栈，则把当前区间[begin,end]出栈进行单趟排序，并让左右子区间[begin,keyi - 1]、[keyi + 1,end]进栈stwhile (!StackEmpty(&st)){//4.1.当前区间[begin,end]出栈进行单趟排序//(1)当前区间出栈。由于栈的后进先出的特性则一定是先当前区间[begin,end]的末尾位置 end先出栈后起始位置begin再出栈。int end = StackTop(&st);//取栈顶元素StackPop(&st);//删除栈顶元素int begin = StackTop(&st);//取栈顶元素StackPop(&st);//删除栈顶元素//(2)当前区间进行单趟排序以此来确定当前区间[begin，end]选定的基准值key在快速排序后 最终位置。int keyi = PartSort1(a, begin, end);//4.2.定义当前区间[begin,end]的左右子区间的范围//(1)左子区间int begin1 = begin, end1 = keyi - 1;//(2)右子区间int begin2 = keyi + 1, end2 = end;//4.3.当前区间[begin,end]]的左右子区间[begin1,end1]、[begin2,end2]进栈st。由于栈 的后进先出的特性使得右子区间先进栈，然后再让左子区间进栈。才能模拟二叉树的前序遍历 思路来实现栈。//(1)若当前区间[begin,end]的右子区间[begin2,end2]只有1个或者0个元素则认为右子 区间[begin2,end2]是个有序区间则不用进栈st。不进栈就不用等出栈列进行单趟排序。if (begin2 < end2){StackPush(&st, begin2);StackPush(&st, end2);}//(2)若当前区间[begin,end]的左子区间[begin1,end1]只有1个或者0个元素则认为左子区间 [begin1,end1]是个有序区间则不用进栈st。不进栈就不用等出栈列进行单趟排序。if (begin1 < end1){StackPush(&st, begin1);StackPush(&st, end1);}}//若栈st此时为空栈，则非递归的快速排序结束了，则此时要销毁栈st。StackDestroy(&st);
}

3.用栈实现非递归快速排序的整个工程

3.1.QuickSortNonR.h

#include<stdio.h>
#include<stdlib.h>
#include<string.h>//以下排序算法都是排升序
//打印函数
void PrintArray(int* a, int n);//交换函数
void Swap(int* p1, int* p2);//直接插入排序
void InsertSort(int* a, int n);//三数取中
// begin  mid  end
int GetMidIndex(int* a, int begin, int end);//Hoare版本的单趟
int PartSort1(int* a, int begin, int end);//挖坑法的单趟
int PartSort2(int* a, int begin, int end);//前后指针的单趟
int PartSort3(int* a, int begin, int end);//二路划分版本的递归快速排序
void QuickSort(int* a, int begin, int end);//非递归的快速排序(借助栈实现)
void QuickSortNonR(int* a, int begin, int end);//NonR->注释：非递归的缩写

3.2.QuickSortNonR.c

#include "Stack.h"
#include "Queue.h"
#include "QuickSortNonR.h"//打印函数
void PrintArray(int* a, int n)
{int i = 0;for (i = 0; i < n; i++){printf("%d ", a[i]);}//换行printf("\n");
}//交换函数
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//直接插入排序
void InsertSort(int* a, int n)
{int i = 0;for (i = 0; i < n - 1; i++){//定义临时变量end从后往前遍历整个有序序列int end = i;//定义变量tmp来临时存放插入数据int tmp = a[end + 1];//直接插入排序的单趟while (end >= 0){if (a[end] > tmp){//挪动数据a[end + 1] = a[end];end--;}else//在有序序列中找小于或等于插入数据tmp，并在它们的后面插入数据tmpbreak;}a[end + 1] = tmp;}}// 三数取中
// begin  mid  end
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end]){return mid;}else if (a[begin] > a[end]){return begin;}else{return end;}}else // a[begin] >= a[mid]{if (a[mid] > a[end]){return mid;}else if (a[begin] < a[end]){return begin;}else{return end;}}
}//Hoare版本的单趟
int PartSort1(int* a, int begin, int end)
{//三数取中int mid = GetMidIndex(a, begin, end);//交换Swap(&a[begin], &a[mid]);int left = begin, right = end;//选区间[begin,end]最左边left位置作为基准值key的下标keyiint keyi = left;while (left < right){//由于选区间[begin,end]最左边left位置的元素做key所以让右边的R先走。//R从右往左遍历区间[begin,end]并且找比基准值key要小的元素。while (left < right){if (a[right] >= a[keyi])right--;elsebreak;}//L从左往右遍历区间[begin,end]并且找比基准值key要大的元素。while (left < right){if (a[left] <= a[keyi])left++;elsebreak;}//由于此时R找到比基准值key要小的数，而此时L找到比基准值key要大的数，则R和L位置的元 素发生交换。if(left < right)Swap(&a[right], &a[left]);}//若L和R相遇则把基准值key与相遇点位置的元素进行交换。注意：此时R和L相遇点位置的元素一定 比基准值key要小。Swap(&a[keyi], &a[left]);keyi = left;//由于一次Hoare版本的单趟结束后，基准值key已经落到它排序后最终位置，所以这里返回基准值 keyi的下标来告诉主调函数基准值key在整个数组中的位置，以防止主调函数继续对基准值key进行 排序。return keyi;
}//挖坑法的单趟
int PartSort2(int* a, int begin, int end)
{//三数取中int mid = GetMidIndex(a, begin, end);//交换Swap(&a[begin], &a[mid]);int hole = begin;//一开始选区间最左边begin位置作为坑位int key = a[hole];//选区间[begin,end]最左边位置begin的元素作为基准值keyint left = begin, right = end;while (left < right){//R从右往左找到比基准值key要小的数后就停下来并把小的数填在左边坑位上后，原来R停下来 的位置变成新的坑位。while (left < right){if (a[right] >= key)right--;else{//把R填在左边坑位中，然后R位置变成新的坑位且这个坑位是在右边。a[hole] = a[right];hole = right;break;}}//L从左往右找到比基准值key要大的数后就停下来并把大的数填在右边坑位上后，原来L停下来 的位置变成新的坑位。while (left < right){if (a[left] <= key)left++;else{//把L填在右边坑位中，然后L位置变成新的坑位且这个坑位是在左边。a[hole] = a[left];hole = left;break;}}}//此时L和R在坑位相遇后就把基准值key填在相遇点的坑位中a[hole] = key;return hole;//单趟结束后放回基准值key在快速排序后的最终位置hole。
}//前后指针的单趟
int PartSort3(int* a, int begin, int end)
{//三数取中int mid = GetMidIndex(a, begin, end);//交换Swap(&a[begin], &a[mid]);//选区间[begin,end]最左边begin位置作为基准值key的下标keyiint keyi = begin;//定义前后指针int prev = begin;int cur = begin + 1;//注意：由于cur是从左往右找比基准值key要小的数，所以在while循环的停止条件应该是cur > end.while (cur <=end){//cur从左往右遍历区间[begin，end]，指针cur一直走直到找到比基准值key要小的数才停下来if (a[cur] >= a[keyi]){cur++;}else{//注意：这里判断++prev == cur的目的是是防止下面这种情况：若prev是一直紧跟着cur 的，当a[cur] < a[keyi]成立时我们没有必要用Swap(&a[prev], &a[cur])函数交换cur位 置和++prev位置的元素，因为此时++prev = cur使得自己交换自己是没有必要的的。案 例：int a[] = {6,1,2,7,9,3,4,5,10,8}.if(++prev != cur)Swap(&a[cur], &a[prev]);cur++;}}//当cur > end时，就把prev位置的元素与基准值key进行交换。交换完后前后指针版本的单趟就结 束了。Swap(&a[keyi], &a[prev]);//由于前后指针版本的单趟结束后，基准值key来到了下标prev的位置，更则要更新keyi的值使 得下标keyi始终指向基准值key。keyi = prev;//由于一次前后指针版本的单趟结束后，基准值key已经落到它排序后最终位置，所以这里返回基准 值keyi的下标来告诉主调函数基准值key在整个数组中的位置，以防止主调函数继续对基准值key进 行排序。return keyi;
}//二路划分版本的递归快速排序
//递归的快速排序->模拟二叉树前序遍历：
void QuickSort(int* a, int begin, int end)
{//若当前待排序区间[begin,end]只有1个或者0个元素则认为当前区间[begin，end]是个有序区间 则此时不需要对有序区间[begin，end]进行快速排序。if (begin >= end)return;//若区间[begin，end]中的元素数量 < 15的话，则直接利用直接插入排序对区间[begin，end]中 的所有元素排序成有序，排完后就直接退出快速排序。if (end - begin + 1 < 15){InsertSort(a + begin, end - begin + 1);//这里使用直接插入排序是为了减少快速排序递 归次数。}else{//模拟二叉树前序遍历实现递归的快速排序：利用单趟排序确定当前区间[begin，end]选定的 基准值key在快速排序后最终位置、递归把当前区间的左子区间[begin，keyi - 1]、右子区间 [keyi + 1,end]排成有序，最终才会使得当前区间[begin,end]变成有序//利用单趟排序确定当前区间[begin，end]选定的基准值key在快速排序后最终位置int keyi = PartSort2(a, begin, end);//递归把当前区间的左子区间[begin，keyi - 1]排成有序区间QuickSort(a, begin, keyi - 1);//递归把当前区间的右子区间[keyi + 1,end]排成有序区间QuickSort(a, keyi + 1, end);}
}//非递归的快速排序->利用栈模拟递归版本快速排序思路(即模拟二叉树的前序遍历思路)
void QuickSortNonR(int* a, int begin, int end)//NonR->注释：非递归的缩写
{if (begin >= end)return;//1.创建栈stST st;//2.堆栈st进行初始化StackInit(&st);//3.当前区间[begin，end]进栈stStackPush(&st, begin);StackPush(&st, end);//4.若栈不为空栈，则把当前区间[begin,end]出栈进行单趟排序，并让左右子区间[begin,keyi - 1]、[keyi + 1,end]进栈stwhile (!StackEmpty(&st)){//4.1.当前区间[begin,end]出栈进行单趟排序//(1)当前区间出栈。由于栈的后进先出的特性则一定是先当前区间[begin,end]的末尾位置 end先出栈后起始位置begin再出栈。int end = StackTop(&st);//取栈顶元素StackPop(&st);//删除栈顶元素int begin = StackTop(&st);//取栈顶元素StackPop(&st);//删除栈顶元素//(2)当前区间进行单趟排序以此来确定当前区间[begin，end]选定的基准值key在快速排序后 最终位置。int keyi = PartSort1(a, begin, end);//4.2.定义当前区间[begin,end]的左右子区间的范围//(1)左子区间int begin1 = begin, end1 = keyi - 1;//(2)右子区间int begin2 = keyi + 1, end2 = end;//4.3.当前区间[begin,end]]的左右子区间[begin1,end1]、[begin2,end2]进栈st。由于栈 的后进先出的特性使得右子区间先进栈，然后再让左子区间进栈。才能模拟二叉树的前序遍历 思路来实现栈。//(1)若当前区间[begin,end]的右子区间[begin2,end2]只有1个或者0个元素则认为右子 区间[begin2,end2]是个有序区间则不用进栈st。不进栈就不用等出栈列进行单趟排序。if (begin2 < end2){StackPush(&st, begin2);StackPush(&st, end2);}//(2)若当前区间[begin,end]的左子区间[begin1,end1]只有1个或者0个元素则认为左子区间 [begin1,end1]是个有序区间则不用进栈st。不进栈就不用等出栈列进行单趟排序。if (begin1 < end1){StackPush(&st, begin1);StackPush(&st, end1);}}//若栈st此时为空栈，则非递归的快速排序结束了，则此时要销毁栈st。StackDestroy(&st);
}

3.3.Stack.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//栈用数组实现，数组的尾部作为栈的栈顶//栈的数据类型
typedef int STDatatype;//栈的结构体类型
typedef struct Stack
{STDatatype* a;int capacity;//容量int top;//统计栈中存放数据的个数。top表示栈顶元素的下一个元素的下标
}ST;//初始化函数
void StackInit(ST* ps);//销毁函数
void StackDestroy(ST* ps);//压栈函数->尾插
void StackPush(ST* ps, STDatatype x);//出栈函数->尾删
void StackPop(ST* ps);//取栈顶元素
STDatatype StackTop(ST* ps);//判断栈是否是空栈
bool StackEmpty(ST* ps);//统计栈中存放数据的个数
int StackSize(ST* ps);//打印函数
void StackPrint(ST* ps);

3.4.Stack.c

#include "stack.h"//初始化函数->把栈st初始化为空栈
void StackInit(ST* ps)
{//判断指针ps是否是空指针assert(ps);ps->a = (STDatatype*)malloc(4 * sizeof(STDatatype));if (ps->a == NULL){perror("malloc fail");exit(-1);}//对栈st的结构体成员进行初始化ps->capacity = 4;ps->top = 0;
}//销毁函数
void StackDestroy(ST* ps)
{//判断指针ps是否是空指针assert(ps);//释放动态空间free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//压栈函数->尾插
void StackPush(ST* ps, STDatatype x)
{//判断指针ps是否为空指针assert(ps);//判断插入位置的合法性assert(ps->top >= 0);//判断栈st的容量是否充足，若不足则要进行扩容。if (ps->top == ps->capacity){//扩容STDatatype* tmp = (STDatatype*)realloc(ps->a, 2 * ps->capacity * sizeof(STDatatype));if (tmp == NULL){perror("malloc fail");exit(-1);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top++] = x;
}//出栈函数->尾删
void StackPop(ST* ps)
{//判断指针ps是否为空指针assert(ps);//判断栈st是否是空栈assert(!StackEmpty(ps));//或者写成assert(ps->top > 0);//判断栈st中是否还有可以删除的元素ps->top--;
}//取栈顶元素
STDatatype StackTop(ST* ps)
{//判断指针ps是否为空指针assert(ps);//判断栈st是否是空栈，若是空栈则没有栈顶元素可取了。assert(!StackEmpty(ps));//或者写成assert(ps->top > 0);//由于top统计的是栈st中存放的数据个数，所以用assert(ps->top > 0)可以判断栈st中是否还有元素，若有则可以取栈顶元素。return ps->a[ps->top - 1];
}//判断栈是否是空栈
bool StackEmpty(ST* ps)
{//判断指针ps是否为空指针assert(ps);判断栈st是否是空栈的写法1：//if (ps->top == 0)//	return true;//else//	return false;//判断栈st是否是空栈的写法2：return ps->top == 0;
}//统计栈中存放数据的个数
int StackSize(ST* ps)
{//判断指针ps是否为空指针assert(ps);return ps->top;
}//打印函数
void StackPrint(ST* ps)
{int i = 0;for (i = 0; i < ps->top; i++)printf("%d ", ps->a[i]);printf("\n");
}

用队列实现非递归快速排序

1.用队列实现非递归快速排序的思路步骤

图形解析：

1.1.思路步骤

• 初始化检查：

  • 如果当前待排序区间 [begin, end] 只有一个或零个元素，则无需排序，直接返回。

• 创建并初始化队列：

  • 创建一个队列 q 用于存储子区间的起始和结束下标。
  • 使用 QueueInit 初始化队列 q 为空队列。

• 入队初始区间：

  • 将初始区间 [begin, end] 的起始下标 begin 和结束下标 end 入队到队列 q 中。

• 循环处理队列中的区间：

  • 当队列 q 不为空时，进入循环处理每个区间。

• 出队并单趟排序：

  • 从队列 q 中出队两个元素，分别作为当前处理的区间的起始下标 begin 和结束下标 end。
  • 对当前区间 [begin, end] 进行单趟排序，确定基准值 key 的最终位置，并返回基准值的索引 keyi。

• 定义左右子区间：

  • 根据基准值的索引 keyi，将当前区间 [begin, end] 划分为左右两个子区间 [begin1, end1] 和 [begin2, end2]。

• 子区间入队：

  • 如果左子区间 [begin1, end1] 包含多于一个元素，则将其入队。
  • 如果右子区间 [begin2, end2] 包含多于一个元素，则将其入队。
  • 由于队列是先进先出的数据结构，左子区间会先入队，然后是右子区间，这保证了子区间的处理顺序与递归快速排序中的顺序一致。

• 结束循环：

  • 当队列为空时，所有子区间都已排序完毕，循环结束。

• 销毁队列：

  • 使用 QueueDestroy 销毁队列 q，释放其占用的内存资源。

1.2.总结

使用队列实现非递归快速排序的思路是用队列模拟二叉树的层序遍历，它按照子区间被分割的顺序来处理它们。在层序遍历中，节点是按照它们在树中的层次顺序被访问的，这对应于快速排序中子区间的分割顺序。处理子区间的顺序是先进先出，这意味着我们会按照子区间被添加到队列中的顺序来处理它们，通常是先处理左子区间，然后是右子区间。具体来说：

• 当一个区间被分割时，其左右子区间被依次加入到队列中。
• 在队列中，最先加入的子区间会最先被处理，这确保了子区间是按照它们被创建的顺序进行排序的。
• 这种顺序保证了每个子区间都会在其父区间之后被处理，符合快速排序中递归处理子区间的逻辑。

因此，使用队列实现非递归快速排序的过程中，子区间的处理顺序确实是按照它们被分割的顺序，从队列的一端进入并在另一端按顺序处理，这与层序遍历中节点的访问顺序相对应。

2.用队列实现非递归快速排序的代码

//非递归的快速排序->利用队列模拟递归版本快速排序思路(即模拟二叉树的前序遍历思路)
void QuickSortNonR(int* a, int begin, int end)//NonR->注释：非递归的缩写
{//若当前待排序区间[begin,end]只有1个或0个元素就没有必要进行快速排序if (begin >= end)return;//1.创建队列qQueue q;//2.对队列q进行初始化，把队列q初始化为空队列q.QueueInit(&q);//3.当前区间[begin，end]入队列q中QueuePush(&q, begin);QueuePush(&q, end);//4.若队列q不为空队列，则把当前区间[begin,end]出队进行单趟排序，并让左右子区间 [begin,keyi - 1]、[keyi + 1,end]入队列.while (!QueueEmpty(&q)){//4.1.当前区间[begin,end]出队进行单趟排序//(1)当前区间出队int begin = QueueFront(&q);//取队头数据QueuePop(&q);//删除队头数据int end = QueueFront(&q);//取队头数据QueuePop(&q);//删除队头数据//(2)当前区间进行单趟排序以此来确定当前区间[begin，end]选定的基准值key在快速排序后 最终位置。int keyi = PartSort1(a, begin, end);//4.2.定义当前区间[begin,end]的左右子区间的范围//(1)左子区间int begin1 = begin, end1 = keyi - 1;//(2)右子区间int begin2 = keyi + 1, end2 = end;//4.3.当前区间[begin,end]]的左右子区间[begin1,end1]、[begin2,end2]入队列q。由于队 列的先进先出的特性使得左子区间先入队，然后再让右子区间入队。//(1)若当前区间[begin,end]的左子区间[begin1,end1]只有1个或者0个元素则认为左子 区间[begin1,end1]是个有序区间则不用入队列q中。不入队列就不用等出队列进行单趟排序。if (begin1 < end1){QueuePush(&q, begin1);QueuePush(&q, end1);}//(2)若当前区间[begin,end]的右子区间[begin2,end2]只有1个或者0个元素则认为右子 区间[begin2,end2]是个有序区间则不用入队列q中。不入队列就不用等出队列进行单趟排序。if (begin2 < end2){QueuePush(&q, begin2);QueuePush(&q, end2);}}//若队列q此时为空队列，则非递归的快速排序结束了，则此时要销毁队列q。QueueDestroy(&q);
}

3.用队列实现非递归快速排序的整个工程

3.1.QuickSortNonR.h

#include<stdio.h>
#include<stdlib.h>
#include<string.h>//以下排序算法都是排升序
//打印函数
void PrintArray(int* a, int n);//交换函数
void Swap(int* p1, int* p2);//直接插入排序
void InsertSort(int* a, int n);//三数取中
// begin  mid  end
int GetMidIndex(int* a, int begin, int end);//Hoare版本的单趟
int PartSort1(int* a, int begin, int end);//挖坑法的单趟
int PartSort2(int* a, int begin, int end);//前后指针的单趟
int PartSort3(int* a, int begin, int end);//二路划分版本的递归快速排序
void QuickSort(int* a, int begin, int end);//非递归的快速排序(借助队列实现)
void QuickSortNonR(int* a, int begin, int end);//NonR->注释：非递归的缩写

3.2.QuickSortNonR.c

#include "Stack.h"
#include "Queue.h"
#include "QuickSortNonR.h"//打印函数
void PrintArray(int* a, int n)
{int i = 0;for (i = 0; i < n; i++){printf("%d ", a[i]);}//换行printf("\n");
}//交换函数
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//直接插入排序
void InsertSort(int* a, int n)
{int i = 0;for (i = 0; i < n - 1; i++){//定义临时变量end从后往前遍历整个有序序列int end = i;//定义变量tmp来临时存放插入数据int tmp = a[end + 1];//直接插入排序的单趟while (end >= 0){if (a[end] > tmp){//挪动数据a[end + 1] = a[end];end--;}else//在有序序列中找小于或等于插入数据tmp，并在它们的后面插入数据tmpbreak;}a[end + 1] = tmp;}}// 三数取中
// begin  mid  end
int GetMidIndex(int* a, int begin, int end)
{int mid = (begin + end) / 2;if (a[begin] < a[mid]){if (a[mid] < a[end]){return mid;}else if (a[begin] > a[end]){return begin;}else{return end;}}else // a[begin] >= a[mid]{if (a[mid] > a[end]){return mid;}else if (a[begin] < a[end]){return begin;}else{return end;}}
}//Hoare版本的单趟
int PartSort1(int* a, int begin, int end)
{//三数取中int mid = GetMidIndex(a, begin, end);//交换Swap(&a[begin], &a[mid]);int left = begin, right = end;//选区间[begin,end]最左边left位置作为基准值key的下标keyiint keyi = left;while (left < right){//由于选区间[begin,end]最左边left位置的元素做key所以让右边的R先走。//R从右往左遍历区间[begin,end]并且找比基准值key要小的元素。while (left < right){if (a[right] >= a[keyi])right--;elsebreak;}//L从左往右遍历区间[begin,end]并且找比基准值key要大的元素。while (left < right){if (a[left] <= a[keyi])left++;elsebreak;}//由于此时R找到比基准值key要小的数，而此时L找到比基准值key要大的数，则R和L位置的元 素发生交换。if(left < right)Swap(&a[right], &a[left]);}//若L和R相遇则把基准值key与相遇点位置的元素进行交换。注意：此时R和L相遇点位置的元素一定 比基准值key要小。Swap(&a[keyi], &a[left]);keyi = left;//由于一次Hoare版本的单趟结束后，基准值key已经落到它排序后最终位置，所以这里返回基准值 keyi的下标来告诉主调函数基准值key在整个数组中的位置，以防止主调函数继续对基准值key进行 排序。return keyi;
}//挖坑法的单趟
int PartSort2(int* a, int begin, int end)
{//三数取中int mid = GetMidIndex(a, begin, end);//交换Swap(&a[begin], &a[mid]);int hole = begin;//一开始选区间最左边begin位置作为坑位int key = a[hole];//选区间[begin,end]最左边位置begin的元素作为基准值keyint left = begin, right = end;while (left < right){//R从右往左找到比基准值key要小的数后就停下来并把小的数填在左边坑位上后，原来R停下来 的位置变成新的坑位。while (left < right){if (a[right] >= key)right--;else{//把R填在左边坑位中，然后R位置变成新的坑位且这个坑位是在右边。a[hole] = a[right];hole = right;break;}}//L从左往右找到比基准值key要大的数后就停下来并把大的数填在右边坑位上后，原来L停下来 的位置变成新的坑位。while (left < right){if (a[left] <= key)left++;else{//把L填在右边坑位中，然后L位置变成新的坑位且这个坑位是在左边。a[hole] = a[left];hole = left;break;}}}//此时L和R在坑位相遇后就把基准值key填在相遇点的坑位中a[hole] = key;return hole;//单趟结束后放回基准值key在快速排序后的最终位置hole。
}//前后指针的单趟
int PartSort3(int* a, int begin, int end)
{//三数取中int mid = GetMidIndex(a, begin, end);//交换Swap(&a[begin], &a[mid]);//选区间[begin,end]最左边begin位置作为基准值key的下标keyiint keyi = begin;//定义前后指针int prev = begin;int cur = begin + 1;//注意：由于cur是从左往右找比基准值key要小的数，所以在while循环的停止条件应该是cur > end.while (cur <=end){//cur从左往右遍历区间[begin，end]，指针cur一直走直到找到比基准值key要小的数才停下来if (a[cur] >= a[keyi]){cur++;}else{//注意：这里判断++prev == cur的目的是是防止下面这种情况：若prev是一直紧跟着cur 的，当a[cur] < a[keyi]成立时我们没有必要用Swap(&a[prev], &a[cur])函数交换cur位 置和++prev位置的元素，因为此时++prev = cur使得自己交换自己是没有必要的的。案 例：int a[] = {6,1,2,7,9,3,4,5,10,8}.if(++prev != cur)Swap(&a[cur], &a[prev]);cur++;}}//当cur > end时，就把prev位置的元素与基准值key进行交换。交换完后前后指针版本的单趟就结 束了。Swap(&a[keyi], &a[prev]);//由于前后指针版本的单趟结束后，基准值key来到了下标prev的位置，更则要更新keyi的值使 得下标keyi始终指向基准值key。keyi = prev;//由于一次前后指针版本的单趟结束后，基准值key已经落到它排序后最终位置，所以这里返回基准 值keyi的下标来告诉主调函数基准值key在整个数组中的位置，以防止主调函数继续对基准值key进 行排序。return keyi;
}//二路划分版本的递归快速排序
//递归的快速排序->模拟二叉树前序遍历：
void QuickSort(int* a, int begin, int end)
{//若当前待排序区间[begin,end]只有1个或者0个元素则认为当前区间[begin，end]是个有序区间 则此时不需要对有序区间[begin，end]进行快速排序。if (begin >= end)return;//若区间[begin，end]中的元素数量 < 15的话，则直接利用直接插入排序对区间[begin，end]中 的所有元素排序成有序，排完后就直接退出快速排序。if (end - begin + 1 < 15){InsertSort(a + begin, end - begin + 1);//这里使用直接插入排序是为了减少快速排序递 归次数。}else{//模拟二叉树前序遍历实现递归的快速排序：利用单趟排序确定当前区间[begin，end]选定的 基准值key在快速排序后最终位置、递归把当前区间的左子区间[begin，keyi - 1]、右子区间 [keyi + 1,end]排成有序，最终才会使得当前区间[begin,end]变成有序//利用单趟排序确定当前区间[begin，end]选定的基准值key在快速排序后最终位置int keyi = PartSort2(a, begin, end);//递归把当前区间的左子区间[begin，keyi - 1]排成有序区间QuickSort(a, begin, keyi - 1);//递归把当前区间的右子区间[keyi + 1,end]排成有序区间QuickSort(a, keyi + 1, end);}
}//非递归的快速排序->利用队列模拟递归版本快速排序思路(即模拟二叉树的层序遍历思路)
void QuickSortNonR(int* a, int begin, int end)//NonR->注释：非递归的缩写
{//若当前待排序区间[begin,end]只有1个或0个元素就没有必要进行快速排序if (begin >= end)return;//1.创建队列qQueue q;//2.对队列q进行初始化，把队列q初始化为空队列q.QueueInit(&q);//3.当前区间[begin，end]入队列q中QueuePush(&q, begin);QueuePush(&q, end);//4.若队列q不为空队列，则把当前区间[begin,end]出队进行单趟排序，并让左右子区间 [begin,keyi - 1]、[keyi + 1,end]入队列.while (!QueueEmpty(&q)){//4.1.当前区间[begin,end]出队进行单趟排序//(1)当前区间出队int begin = QueueFront(&q);//取队头数据QueuePop(&q);//删除队头数据int end = QueueFront(&q);//取队头数据QueuePop(&q);//删除队头数据//(2)当前区间进行单趟排序以此来确定当前区间[begin，end]选定的基准值key在快速排序后 最终位置。int keyi = PartSort1(a, begin, end);//4.2.定义当前区间[begin,end]的左右子区间的范围//(1)左子区间int begin1 = begin, end1 = keyi - 1;//(2)右子区间int begin2 = keyi + 1, end2 = end;//4.3.当前区间[begin,end]]的左右子区间[begin1,end1]、[begin2,end2]入队列q。由于队 列的先进先出的特性使得左子区间先入队，然后再让右子区间入队。//(1)若当前区间[begin,end]的左子区间[begin1,end1]只有1个或者0个元素则认为左子 区间[begin1,end1]是个有序区间则不用入队列q中。不入队列就不用等出队列进行单趟排序。if (begin1 < end1){QueuePush(&q, begin1);QueuePush(&q, end1);}//(2)若当前区间[begin,end]的右子区间[begin2,end2]只有1个或者0个元素则认为右子 区间[begin2,end2]是个有序区间则不用入队列q中。不入队列就不用等出队列进行单趟排序。if (begin2 < end2){QueuePush(&q, begin2);QueuePush(&q, end2);}}//若队列q此时为空队列，则非递归的快速排序结束了，则此时要销毁队列q。QueueDestroy(&q);
}

3.3.Queue.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>//队列的数据类型
typedef int QDataType;//队列链表的结点类型
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列的结构体类型
typedef struct Queue
{QNode* head;//指针head指向队列队头数据。QNode* tail;//指针tail指向队列队尾数据。int size;//统计队列存储数据的个数
}Queue;//初始化函数
void QueueInit(Queue* pq);//销毁函数
void QueueDestroy(Queue* pq);//入队函数->尾插(插入数据)
void QueuePush(Queue* pq, QDataType x);//出队函数->头删(删除数据)
void QueuePop(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataType QueueBack(Queue* pq);//判断队列是否是空队列
bool QueueEmpty(Queue* pq);//统计队列中存放数据的个数
int QueueSize(Queue* pq);//打印函数
void QueuePrint(Queue* pq);

3.4.Queue.c

#include "Queue.h"//初始化函数->目的：把队列q初始化为空队列
void QueueInit(Queue* pq)
{//判断指针pq是否是空指针assert(pq);//对队列q的结构体成员进行初始化//由于队列最初状态是个空队列使得当用单链表实现队列时单链表最初的状态也是空链表，而要使得指针pq->head指向的链表是个空链表，则只需把指针pq->head的值设置为空指针NULL即可。pq->head = pq->tail = NULL;//由于队列一开始是个空队列使得让队头指针pq->head和队尾指针pq->tail一开始指向空链表。pq->size = 0;
}//销毁函数
void QueueDestroy(Queue* pq)
{//判断指针pq是否是空指针assert(pq);//由于队头指针pq->head始终是指向队头数据的，所以想要遍历整个链表的话则我们需要定义一个临时指针cur遍历链表。QNode* cur = pq->head;while (cur)//当cur指向NULL，则遍历链表结束。{//用指针del保存当前要销毁结点的地址QNode* del = cur;//注意：必须是先让cur移动到下一个结点的位置后再删除del位置的结点。cur = cur->next;free(del);}//当链表的所有结点都删除完后必须把队头指针和队尾指针都设置成空指针，否则没有置为空指针的话若通过主调函数队列的结构体访问到队头指针和队尾指针的话会造成对野指针进行访问的风险。pq->head = pq->tail = NULL;pq->size = 0;
}//入队函数->尾插(插入数据)
//注意：由于在队列的所有功能函数中只有入队函数QueuePush才会增加队列的数据个数，
//而其他队列的功能函数都没有增加队列数据的个数，所以不需要单独写一个函数来创建队列链表的结点。
void QueuePush(Queue* pq, QDataType x)
{//判断指针pq是否是空指针assert(pq);//创建结点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}//对新创建结点的成员变量进行初始化newnode->data = x;newnode->next = NULL;//判断是否是头插if (pq->head == NULL)//或者写成if (pq->tail == NULL)pq->head = pq->tail = newnode;else//尾插{//把新创建的结点和队尾结点链接起来pq->tail->next = newnode;//让队尾指针指向新的队尾结点pq->tail = newnode;}pq->size++;
}写法1：出队函数->头删(删除数据)
//void QueuePop(Queue* pq)
//{
//	//判断指针pq是否是空指针
//	assert(pq);
//
//	//判断队列是否是空队列，若是空队列则不继续删除队头数据。
//	assert(!QueueEmpty(pq));
//
//	//判断链表是否删除到还剩一个结点->这里要判断这种情况的原因是：由于我们会使用队头指针和队尾指针判断队列是否是空队列，当队列还剩一个结点而且还要进行头删的时候，
//	//若没有if语句的判断只执行else语句的内容会使得即使队头指针pq->head会被赋值成空指针NULL，但是队尾指针pq->tail会变成野指针，这样会在QueueEmpty函数中发生对野指针pq->tail进行解引用。
//	if (pq->head->next == NULL)
//	{
//		free(pq->head);
//		//这种情况一定要把队头指针head和队尾指针tail置成空指针NULL，否则在判断队列是否是空队列时会发生对野指针进行解引用的风险
//		pq->head = pq->tail = NULL;
//	}
//	else//头删
//	{
//		//保存当前要删除结点的地址
//		QNode* del = pq->head;
//
//		//注意：必须先让队头指针指向新的队头结点后再删除del位置的结点。
//		//让队头指针指向新的队头结点
//		pq->head = pq->head->next;
//		//删除del位置的结点
//		free(del);
//	}
//	pq->size--;
//}//写法2：出队函数->头删(删除数据)
void QueuePop(Queue* pq)
{//判断指针pq是否是空指针assert(pq);//判断队列是否是空队列assert(!QueueEmpty(pq));//头删的过程：//保存当前要删除的结点QNode* del = pq->head;//注意：必须先让队头指针指向新的队头结点后再删除del位置的结点。pq->head = pq->head->next;//换头//删除结点free(del);if (pq->head == NULL)//若队头指针pq->head = NULL说明此时队列被删除成空队列，但是此时队尾指针pq->tail为野指针，则此时必须把野指针pq->tail设置成空指针。pq->head = pq->tail = NULL;pq->size--;
}//取队头数据
QDataType QueueFront(Queue* pq)
{//判断指针pq是否是空指针assert(pq);//判断队列是否是空队列，若队列为空则不需要取队头数据了。assert(!QueueEmpty(pq));return pq->head->data;//由于指针pq->head指向队列队头结点，所以只需通过队头指针访问队头结点中存放的数据即可。
}//取队尾数据
QDataType QueueBack(Queue* pq)
{//判断指针pq是否是空指针assert(pq);//判断队列是否是空队列，若队列为空则不需要取队尾数据了。assert(!QueueEmpty(pq));return pq->tail->data;//由于指针pq->head指向队列队尾结点，所以只需通过队头指针访问队尾结点中存放的数据即可。
}//判断队列是否是空队列
bool QueueEmpty(Queue* pq)
{//判断指针pq是否是空指针assert(pq);return (pq->head == NULL) && (pq->tail == NULL);//只有队头指针和队尾指针同时为空指针才能说明队列是个空队列
}//统计队列中存放数据的个数
int QueueSize(Queue* pq)
{//判断指针pq是否是空指针assert(pq);写法1：时间复杂度O(N)//int size = 0;//QNode* cur = pq->head;//while (cur)//{//	cur = cur->next;//	size++;//}//return size;//写法2：时间复杂度O(1)return pq->size;
}//打印函数
void QueuePrint(Queue* pq)
{//判断指针pq是否是空指针assert(pq);QNode* cur = pq->head;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

总结

用栈实现非递归快速排序：

模拟前序遍历：

• 栈用于模拟快速排序的递归调用栈，这相当于模拟二叉树的前序遍历。。在递归快速排序中，每次递归调用都会将新的子区间信息（起始和结束索引）保存在调用栈上。
• 在非递归实现中，我们手动将这些子区间的信息压入栈中，从而模拟递归的调用过程。
• 处理子区间的顺序是后进先出，这意味着我们会先处理最近添加到栈中的子区间，通常是右子区间，然后是左子区间。

用队列实现非递归快速排序：

模拟层序遍历：

• 队列用于模拟二叉树的层序遍历，它按照子区间被分割的顺序来处理它们。
• 在层序遍历中，节点是按照它们在树中的层次顺序被访问的，这对应于快速排序中子区间的分割顺序。
• 处理子区间的顺序是先进先出，这意味着我们会按照子区间被添加到队列中的顺序来处理它们，通常是先处理左子区间，然后是右子区间。