前言

为什么要学习非递归写法呢？
当我们在用递归实现一个程序的时候，要考虑一个问题，这个程序用递归去实现，当数据量庞大的时候，会不会造成栈溢出(STACK OVERFLOW)呢？
如果没有造成还好，造成了怎么解决这个问题呢？这个时候就需要用到非递归，把一个递归实现的程序转化为非递归，是一个程序猿的基本功。

int Sum(int n)
{if (n == 1){return 1;}return n + Sum(n - 1);
}int main()
{int ret = Sum(100);cout << ret;return 0;
}

比如这个代码，把这个代码转化为非递归特别简单，一个for循环即可搞定。

	int ret = 0;for (int i = 1; i <= 100; i++){ret += i;}cout << ret;

那么一个复杂的代码呢？比如快速排序，归并排序

快速排序非递归

快速排序在递归的时候，每次都是把区间压入栈中，
这是一个快排的代码，前后指针版本的。

从代码的最后，每次都是把基准值的左面先压入栈中，然后在继续划分，直到不能在划分为止，这个时候，就开始划分基准值的右面，直到完成排序。根据这个思想我们可以考虑手动模拟一个栈，然后用非递归来实现快排。

C++有库函数可以直接使用，在这里就不再写栈是怎么实现的了，不会的点击->传送门。
因为是把栈的左右区间压入，还要在定义一个pair<int,int>,不知道这个是什么的，也可以使用结构体，让结构体里面存左右区间也行

typedef pair<int, int> PII;typedef struct Stack
{int l, r;
}stk;

1. 首先，把最开始的区间压入栈中，然后以栈是否为空做为循环条件进行判断
2. 定义临时变量存储左(begin)右(end)区间，然后用我们之前学过的快排，来模拟这一过程，快排里不在使用递归。
3. 将区间划分，并压入栈中
4. 重复2和3，直到循环结束，此时排序完成

代码如下

//挖坑法的快排代码
int PartSort2(int* a, int l, int r)
{//if (l >= r)//{//	return;//}int key = a[l];int hole = l;int bg = l;int ed = r;while (l < r){while (l < r && a[r] >= key){r--;}a[hole] = a[r];hole = r;while (l < r && a[l] <= key){l++;}a[hole] = a[l];hole = l;}a[hole] = key;return hole;
}//非递归形式实现快排
void QuickSort(int* a, int l, int r)
{stack<PII> stk;stk.push({ l, r });while (!stk.empty()){auto t = stk.top();stk.pop();int begin = t.first;int end = t.second;if (begin >= end){continue;}int key_i = PartSort2(a, begin, end);stk.push({ begin,key_i - 1 });stk.push({ key_i + 1, end });}
}

归并排序的非递归

归并排序的非递归，这玩意有难度，学了好久才学会。
归并排序并不是用栈去实现的，因为归并排序是八一个序列分成n个子序列，然后归并归并归并，得到一个呈上升或者下降的序列，从这里，我们可以考虑直接从n个子序列开始归并，类似于树的后续遍历。
这里就要个问题了，归并排序需要一个临时数组，然后把临时数组赋值给原数组，从而得到有序序列，那么，这个拷贝的过程是一次性拷贝完，还是归并一次拷贝一次呢？
答案是这两种方式都可以，直接拷贝完的话呢，需要考虑的情况有点多，不推荐，归并一次拷贝一次最好。

1. 首先定义一个gap，gap表示几几归并，刚开始肯定是一一归并，然后二二归并，四四归并

for (int i = 0; i < n; i += 2 * gap)

2. 创建临时变量，将序列分隔开，

int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;//建议自己手动模拟一下这个过程

4. 对边界问题进行修正

if (end1 >= n || begin2 >= n)
{break;
}if (end2 >= n)
{end2 = n - 1;
}

4. 开始归并

while (begin1 <= end1 && begin2 <= end2)
{if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}
}while (begin1 <= end1)
{tmp[j++] = a[begin1++];
}while (begin2 <= end2)
{tmp[j++] = a[begin2++];
}

5. 将临时数组拷贝到原数组中

memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));

6. 将gap扩大

		gap *= 2;

7. 重复上述2，3，4，5，6操作
8. 释放掉临时数组

	free(tmp);

代码如下

void UMergeSort(int* a, int n ,int* tmp)
{int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * (n));UMergeSort(a, n,tmp);}