空间-排序的递归问题：能否用函数指针以及栈代替递归？？

问题描述

排序的递归问题：能否用函数指针以及栈代替递归？？
最近学习排序，对于快排，归并等处理海量数据效率高的算法很钟意，但是其自身的递归特性有很多缺点，譬如数据量过大时存在溢出的风险，也影响了算法的效率，故想到用栈代替递归这一过程。大致想法就是创建个函数指针类型的栈，然后将每个子排序的函数指针压入其中，然后再一个一个用*解引用来运行函数。当然我知道改成非递归有别的方法，但是可能会比这复杂，就想考虑用栈来实现。我想知道的是，对于快排和归并等递归排序算法，用以上方法实现的话，算法的开销（时间复杂度和空间复杂度），以及实际效率会是如何，有实际意义么。问题描述不全，毕竟第一次在CSDN提问，望前辈们多看看。本人大二，学了c++ java。

解决方案

http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

解决方案二：
完全可行，而且使用自己的栈或者递归，相同的算法的时间复杂度空间复杂度是没有变化的。

解决方案三：
quicksort有in-place的实现，不需要额外的栈啊。至于mergesort，你也不需要栈，只需要一个可以copy的数组

时间： 2024-08-30 22:39:15

空间-排序的递归问题：能否用函数指针以及栈代替递归？？的相关文章

常见的五类排序算法图解和实现（交换类：冒泡排序，递归的快速排序）

冒泡排序算法: 总的来说就是两两交换,反复直到有序,第一个记录和第二个记录,若逆序则交换,然后比较第二个和第三个记录,以此类推,直到第 n 个记录和第 n-1个记录比较完毕为止,第一趟排序,结果关键字最大的记录被安排在最后一个位置.对前 n-1个记录继续冒泡排序,使得关键字次大的记录安排在第 n-1个位置.如此重复,直到没有需要交换的记录为止(仅仅是第一个和第二个交换过为止).整个一趟趟的选出最值的过程,仿佛是那水里的气泡,咕嘟咕嘟的往上翻的过程. 递增冒泡排序过程图解: 一般先比较第一个元素和

C++函数的嵌套调用和递归调用学习教程_C 语言

C++函数的嵌套调用 C++不允许对函数作嵌套定义,也就是说在一个函数中不能完整地包含另一个函数.在一个程序中每一个函数的定义都是互相平行和独立的. 虽然C++不能嵌套定义函数,但可以嵌套调用函数,也就是说,在调用一个函数的过程中,又调用另一个函数. 在程序中实现函数嵌套调用时,需要注意的是:在调用函数之前,需要对每一个被调用的函数作声明(除非定义在前,调用在后). [例]用弦截法求方程f(x)=x3-5x2+16x-80=0的根. 这是一个数值求解问题,需要先分析用弦截法求根的算法.根据数学知

Python和PHP如何使用递归建立多层目录函数

在用到写缓存时,常常会遇到建立多个多层目录的操作,这种操作我们手工去操作太繁琐了,今天我们就来看一下使用python递归建立多层目录的方法: 首先上代码: #! /usr/bin/env python #coding=utf-8 import os def mkFolder(path): if not os.access(path,os.R_OK): #print 1212 #print os.path.dirname(path) path_last = len(path)-1 if path[

非递归二叉树遍历-c语言中函数指针作为参数与函数的嵌套

问题描述 c语言中函数指针作为参数与函数的嵌套 函数指针作为另一函数的参数和函数的嵌套的区别,感觉都是调用,有什么不一样呢?他们都适用在什么情况下!(我是在学非递归遍历二叉树时看到的) Status Visit(TElemType e){ printf("%cn",e); return OK; } Status InOrderTraverse(BiTree T ,Status(*Visit)(TElemType e)){ SqStack S; InitStack(S); Push(S,

c++-C++ 6.0结构体字段多重排序的函数指针

问题描述 C++ 6.0结构体字段多重排序的函数指针 C++对结构体数组进行排序,排序结果存在紊乱,库函数的函数指针怎么解决排序紊乱的问题? 解决方案 参考:http://blog.csdn.net/lethic/article/details/7781203 解决方案二: 运算符重载,大于号重新定义,然后直接sort 解决方案三: 需要定义使用结构体的哪个成员作为排序用的key,然后对该key定义小于运算符重载,进行排序.

函数指针和数组指针的区别，函数指针在结构体中怎么实现排序？

问题描述 函数指针和数组指针的区别,函数指针在结构体中怎么实现排序? 求咨询下,结构体浮点数组的排序,多重条件用函数指针传参数给库函数怎么实现排序呢? 解决方案 参考:http://blog.csdn.net/lethic/article/details/7781203 解决方案二: 函数指针及结构体 解决方案三: 函数指针:指向函数入口的指针,为指向代码段的一个地址. 数组指针:指向数组的指针.

实例解析C++中类的成员函数指针_C 语言

C语言的指针相当的灵活方便,但也相当容易出错.许多C语言初学者,甚至C语言老鸟都很容易栽倒在C语言的指针下.但不可否认的是,指针在C语言中的位置极其重要,也许可以偏激一点的来说:没有指针的C程序不是真正的C程序. 然而C++的指针却常常给我一种束手束脚的感觉.C++比C语言有更严格的静态类型,更加强调类型安全,强调编译时检查.因此,对于C语言中最容易错用的指针,更是不能放过:C++的指针被分成数据指针,数据成员指针,函数指针,成员函数指针,而且不能随便相互转换.而且这些指针的声明格式都不一样:

指针数组，数组指针，指针函数，函数指针，二级指针详解

先看个简单的:char *p,这定义了一个指针,指针指向的数据类型是字符型,char  *(p)定义了一个指针P: char *p[4], 为指针数组,由于[]的优先级高于*,所以p先和[]结合,p[]是一个数组,暂时把p[]看成是q,也就是char *(q),定义了一个指针q,只不过q是一个数组罢了,故定义了一个数组,数组里面的数据是char *的,所以数组里面的数据为指针类型.所以char *p[4]是四个指针,这四个指针组成了一个数组,称为指针数组,既有多个指针组成的数组. char(*p

函数指针和指针函数

1.函数指针(指向函数的指针) 在c语言中,一个函数总是占用一段连续的内存区,而函数名就是该函数所占内存区的首地址(入口地址),所以函数名跟数组名很类似,都是指针常量. 函数指针就是指向这个入口地址的指针变量,注意函数指针是一个变量. #include<stdio.h> void f(int); int main() { //定义函数指针pf并给pf赋值使其指向函数f的入口地址 //pf先跟*结合,说明pf是一个指针,然后与括号结合,说明这个指针指向函数 void (*pf)(int)=f;