学习非递归之前我们得先学习递归的缺陷，才能更好了解非递归的优势。
递归的缺陷：栈帧空间太深，栈空间不够用，会导致溢出。
c语言内存分配：
例如：
递归1000次：
递归10000次：
图解：
递归（函数调用）是进行压栈的操作，当压栈太深时，就会造成栈溢出的情况。
递归改非递归方法：①直接改循环 ②借助数据结构栈模拟递归过程
1、快速排序非递归
我们来运用非递归实现快速排序挖坑法
1.1代码实现
栈的操作，大家可以看阿紫之前发的“不会2022年还有人不懂栈吧”这篇博文哦！
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include"stack.h" //挖坑法 - 升序 int PartSort(int* a, int left, int right) { int begin = left; int end = right; int key = a[begin]; int pivot = begin; while (begin < end) { while (begin < end && a[end] >= key) { --end; } a[pivot] = a[end]; pivot = end; while (begin < end && a[begin] <= key) { ++begin; } a[pivot] = a[begin]; pivot = begin; } pivot = begin;//当begin与end相遇，随便把begin和end的值给pivot a[pivot] = key; return pivot; } //快速排序非递归 void QuickSortNonR(int* a, int n) { ST st; StackInit(&st);//初始化栈 StackPush(&st, n - 1);//入数组最后一个元素下标 StackPush(&st, 0);//入数组第一个元素下标 while (!StackEmpty(&st))//当栈不为空我们就进入循环 { int left = StackTop(&st);//取出栈顶元素给left StackPop(&st);//出栈 - 删除栈顶元素 int right = StackTop(&st); StackPop(&st); int keyIndex = PartSort(a, left, right);//使用挖坑法区间排序 //[left, keyIndex - 1] keyIndex [keyIndex + 1, right] - 分成子区间 if (keyIndex + 1 < right)//因栈后进先出的特性，所以先入右区间 { StackPush(&st, right); StackPush(&st, keyIndex + 1); } if (left < keyIndex - 1) { StackPush(&st, keyIndex - 1); StackPush(&st, left); } } StackDestory(&st);//销毁栈 } int main() { int arr[10] = {3, 4, 2, 5, 1}; int sz = sizeof(arr) / sizeof(arr[0]); QuickSortNonR(arr, sz); for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
1.2思路讲解
我们根据上面的代码来学习思路
2、归并排序非递归
2.1代码实现
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include"stack.h" //归并排序之非递归 void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int)* n); if (tmp == NULL) { perror("malloc:"); return; } int gap = 1;//gap为每组数据的个数，每次翻倍 while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { //可以看成 [i, i + gap - 1] [i + gap, i + 2 * gap - 1] int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; //归并过程中右半区间有可能不存在！ if (begin2 >= n) break; //归并过程中右半区间越界了，就修正 if (end2 >= n) { end2 = n - 1; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //拷贝进去 for (int j = i; j <= end2; ++j) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); } int main() { int arr[] = {10, 6, 7, 1, 3, 9, 4, 2 }; int sz = sizeof(arr) / sizeof(arr[0]); MergeSortNonR(arr, sz); for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; }
2.2思路讲解
