有一天我用水壶烧水的时候

不小心水放满了

于是当它烧沸腾的时候

水一直往外冒

我便想起了递归导致栈溢出的情况

于是阿紫姐姐便在网上学习了非递归算法

接下来阿紫姐姐传授给大家哦!

本期阿紫姐姐就带领大家一起来学习快速排序、归并排序非递归的实现哦!!!

目录:

1、快速排序非递归

2、归并排序非递归

学习非递归之前我们得先学习递归的缺陷,才能更好了解非递归的优势。

递归的缺陷:栈帧空间太深,栈空间不够用,会导致溢出。

 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思路讲解

 

 

 

技术
©2019-2020 Toolsou All rights reserved,
在算法研究过程中如何进行算法创新七大排序算法(java代码)MYSQL中的索引与事务———javaweb(8)(面试必考)2022蓝桥杯JavaB组省赛试题网络安全-wifi攻防网络层协议——ICMP协议MySQL查询表中指定条件下的最新记录JavaSE笔记(一)Java基础语法mysql 查询条件之外的数据_mysql 查询符合条件的数据qt使用数据库sqlite