本篇内容引发于下图问题，下面将分别给出递归与使用另一个栈的实现。
一、只用一个栈的递归实现栈的排序：
核心函数：
void SqSort(SqStack& s) {
if (s.top != s.base) {
int temp;
Pop(s, temp); // 移除栈顶元素
SqSort(s); // 递归排序剩余的栈
InsertSortedStack(s, temp); // 将移除的元素插入排序好的栈中
}
}
void InsertSortedStack(SqStack& s, int e) {
if (s.top == s.base || GetTop(s) <= e) {
Push(s, e); // 如果栈为空或栈顶小于等于元素，则插入
} else {
int temp;
Pop(s, temp); // 否则弹出栈顶元素，递归插入
InsertSortedStack(s, e);
Push(s, temp); // 重新将弹出的元素压栈
}
}核心思想
- 递归移除栈顶元素：不断从栈中弹出元素，直到栈为空（或只有一个元素）。这相当于将问题分解为处理更小的子栈。
- 将弹出的元素插入回已排序的栈：当栈变为空时，从递归调用返回，在返回的过程中，将每个弹出的元素插入到已排序的子栈中。这个插入操作需要保证栈中的元素始终保持顺序。
算法步骤
- 递归基准情况：如果栈为空或只有一个元素，则直接返回，递归结束。这是递归的停止条件。
- 弹出栈顶元素：从栈中移除栈顶元素，将其保存到临时变量中。
- 递归调用自身：对剩下的栈（不包括弹出的元素）进行递归排序。递归调用继续，直到栈为空。
- 插入栈顶元素：在递归返回时，将刚才弹出的元素插入到已排序的子栈中，确保插入后栈仍然是有序的。
- 恢复栈的完整性：通过在递归返回过程中逐步将元素按正确顺序插入，栈最终被排序。
具体步骤实现
- 递归函数
SqSort：- 检查栈是否为空或只有一个元素，如果是，递归结束。
- 弹出栈顶元素，并递归排序剩余的栈。
- 递归返回后，调用
InsertSortedStack，将栈顶元素按顺序插回栈。
- 辅助函数
InsertSortedStack：- 检查栈是否为空，或者栈顶元素是否小于等于要插入的元素。如果是，则直接将元素压栈。
- 否则，弹出栈顶元素，递归调用自身，将元素插入剩余栈中，再将弹出的栈顶元素压栈。
时间复杂度：
- 时间复杂度：栈中的每个元素都会被弹出并重新插入栈，因此时间复杂度为 O(n^2)，其中 n 是栈中的元素个数。
- 空间复杂度：由于使用递归，每次递归调用都会占用栈空间，空间复杂度为 O(n)。
完整代码及测试：
#include <iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct
{
int* base;
int* top;
int stacksize;
}SqStack;
Status InitStack(SqStack& S)
{//栈初始化
S.base = new int[MAXSIZE];
if (!S.base)
return ERROR;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
Status Push(SqStack& S, int e)
{//入栈
if (S.top - S.base >= S.stacksize)
return OVERFLOW;
*S.top++ = e;
return OK;
}
Status Pop(SqStack& S,int &e)
{//出栈
if (S.top == S.base)
return ERROR;
e=*--S.top;
return OK;
}
int GetTop(SqStack S)
{//取栈顶元素
if (S.top == S.base)
return ERROR;
return *(S.top - 1);
}
void Out(SqStack s) {
int* flag = s.top;
while (flag > s.base) {
cout << *(flag - 1) << " ";
flag--;
}
cout << endl;
}
// 将元素插入到已排序的栈中的正确位置
void InsertSortedStack(SqStack &s, int e) {
if (s.top == s.base || GetTop(s) <= e) {
Push(s, e); // 如果栈为空或栈顶元素小于等于当前元素，则直接入栈
}
else {
int temp = 0;
Pop(s, temp); // 否则，弹出栈顶元素
InsertSortedStack(s, e); // 递归调用将元素插入到正确的位置
Push(s, temp); // 插入完成后，将之前弹出的元素重新压栈
}
}
// 递归排序栈
void SqSort(SqStack& s) {
if (s.top != s.base) {
int temp = 0;
Pop(s, temp); // 移除栈顶元素
SqSort(s); // 递归排序剩余的栈
InsertSortedStack(s, temp); // 将移除的元素插入到已排序的栈中
}
}
int main()
{
SqStack s;
InitStack(s);
Push(s, 4);
Push(s, 2);
Push(s, 6);
Push(s, 5);
Push(s, 1);
Push(s, 3);
Out(s);
SqSort(s);
Out(s);
}输出：
3 1 5 6 2 4
6 5 4 3 2 1
二、使用另一个栈实现栈的排序：
核心函数
void SqSort(SqStack& s) {
SqStack ts;//辅助栈
InitStack(ts);
while (s.top > s.base) {
int temp1 = 0;
Pop(s, temp1);
//当辅助栈为空或者取出元素小于辅助栈栈顶元素时将temp1入辅助栈
if (ts.base == ts.top || GetTop(ts) >= temp1) {
Push(ts, temp1);
}
else {//当取出元素大于辅助栈栈顶元素时,将辅助栈内元素放回原栈，直到temp1小于辅助栈栈顶元素
while (ts.base != ts.top&& GetTop(ts) < temp1){//注意此处的条件
int temp2 = 0;
Pop(ts, temp2);
Push(s, temp2);
}//由于辅助栈内是排好序的，按顺序取出入原栈，依然有序，放入temp1后这些元素将再次返回辅助栈
Push(ts, temp1);
}
}
//排序后将辅助栈元素返回到原栈中
while (ts.base != ts.top) {
int e;
Pop(ts, e);
Push(s, e);
}
}核心思想
该排序算法利用辅助栈对主栈中的元素进行排序。通过逐个弹出主栈中的元素，依次与辅助栈的栈顶元素比较，有序地放入辅助栈。当主栈元素较大时直接入辅助栈；当主栈元素较小时，将辅助栈中的较大元素重新放回主栈，直到找到适当位置，再将较小元素放入辅助栈。最后将辅助栈元素放回主栈。
算法步骤
- 初始化一个辅助栈
ts。 - 从主栈
s逐一弹出元素：- 如果辅助栈为空，或当前弹出的元素不大于辅助栈的栈顶元素，则将该元素直接推入辅助栈。
- 否则，反复将辅助栈中比当前元素大的元素弹出，推回主栈，直到找到合适位置，再将当前元素放入辅助栈。
- 重复上述过程，直到主栈中的所有元素都按顺序存入辅助栈。
- 最后，将辅助栈中的元素依次弹出，重新放回主栈，使得主栈从栈底到栈顶为从小到大的顺序。
复杂度分析
时间复杂度
- 最坏情况：在最坏情况下（即主栈中的元素按逆序排列时），每次需要将辅助栈中大量元素重新放回主栈，导致大量的元素被反复移动。因此，最坏情况的时间复杂度为 O(n²)，其中
n是栈中元素的数量。 - 最好情况：在最好情况下（即主栈中的元素已经按顺序排列时），每个元素只需要移动一次，时间复杂度为 O(n)。
空间复杂度
该算法使用了一个额外的辅助栈，因此空间复杂度为 O(n)，其中 n 为栈中元素的数量。
完整代码及测试：
#include <iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
using namespace std;
typedef struct
{
int* base;
int* top;
int stacksize;
}SqStack;
Status InitStack(SqStack& S)
{//栈初始化
S.base = new int[MAXSIZE];
if (!S.base)
return ERROR;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
Status Push(SqStack& S, int e)
{//入栈
if (S.top - S.base >= S.stacksize)
return OVERFLOW;
*S.top++ = e;
return OK;
}
Status Pop(SqStack& S, int& e)
{//出栈
if (S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}
int GetTop(SqStack S)
{//取栈顶元素
if (S.top == S.base)
return ERROR;
return *(S.top - 1);
}
void Out(SqStack s) {
int* flag = s.top;
while (flag > s.base) {
cout << *(flag - 1) << " ";
flag--;
}
cout << endl;
}
void SqSort(SqStack& s) {
SqStack ts;//辅助栈
InitStack(ts);
while (s.top > s.base) {
int temp1 = 0;
Pop(s, temp1);
//当辅助栈为空或者取出元素小于辅助栈栈顶元素时将temp1入辅助栈
if (ts.base == ts.top || GetTop(ts) >= temp1) {
Push(ts, temp1);
}
else {//当取出元素大于辅助栈栈顶元素时,将辅助栈内元素放回原栈，直到temp1小于辅助栈栈顶元素
while (ts.base != ts.top&& GetTop(ts) < temp1){//注意此处的条件
int temp2 = 0;
Pop(ts, temp2);
Push(s, temp2);
}//由于辅助栈内是排好序的，按顺序取出入原栈，依然有序，放入temp1后这些元素将再次返回辅助栈
Push(ts, temp1);
}
}
//排序后将辅助栈元素返回到原栈中
while (ts.base != ts.top) {
int e;
Pop(ts, e);
Push(s, e);
}
}
int main()
{
SqStack s;
InitStack(s);
Push(s, 4);
Push(s, 2);
Push(s, 6);
Push(s, 5);
Push(s, 1);
Push(s, 3);
Out(s);
SqSort(s);
Out(s);
}输出：
3 1 5 6 2 4
6 5 4 3 2 1
那么问题来了，用队呢？
询问GPT得到肯定的答案，此处我没有加以验证，也不再追述。