C++ 中快排的递归和非递归实现
快排的递归
void quickSort1(int* root,int low,int high) { int pat=root[low]; if(low<high) { int i=low,j=high; while(i<j) { while(i<j&&root[j]>pat) j--; root[i]=root[j]; while(i<j&&root[i]<pat) i++; root[j]=root[i]; } root[i]=pat; quickSort1(root,low,i-1); quickSort1(root,i+1,high); } }
快排的非递归
int partion(int* root,int low,int high) { int part=root[low]; while(low<high) { while(low<high&&root[high]>part) high--; root[low]=root[high]; while(low<high&&root[low]<part) low++; root[high]=root[low]; } root[low]=part; return low; } void quickSort2(int* root,int low,int high) { stack<int> st; int k; if(low<high) { st.push(low); st.push(high); while(!st.empty()) { int j=st.top();st.pop(); int i=st.top();st.pop(); k=partion(root,i,j); if(i<k-1) { st.push(i); st.push(k-1); } if(k+1<j) { st.push(k+1); st.push(j); } } } } int main() { int a[8]={4,2,6,7,9,5,1,3}; quickSort1(a,0,7); //quickSort2(a,0,7); int i; for(i=0;i<8;i++) cout<<a[i]<<" "; cout<<endl; getchar(); return 0; }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关推荐
-
C++多继承多态的实例详解
C++多继承多态的实现 如果一个类中存在虚函数,在声明类的对象时,编译器就会给该对象生成一个虚函数指针,该虚函数指针指向该类对应的虚函数表. 多态的实现是因为使用了一种动态绑定的机制,在编译期间不确定调用函数的地址,在调用虚函数的时候,去查询虚函数指针所指向的虚函数表. 派生类生成的对象中的虚函数指针指向的是派生类的虚函数表,因此无论是基类还是派生来调用,都是查询的是派生类的表,调用的是派生类的函数. 如果发生了多继承,多个基类中都有虚函数,那么该是怎样的呢?虚函数指针如何排列,多个基类的指针为
-
C++ 中消息队列函数实例详解
C++ 中消息队列函数实例详解 1.消息队列结构体的定义 typedef struct{ uid_t uid; /* owner`s user id */ gid_t gid; /* owner`s group id */ udi_t cuid; /* creator`s user id */ gid_t cgid; /* creator`s group id */ mode_t mode; /* read-write permissions 0400 MSG_R 0200 MSG_W*/ ul
-
C++实现稀疏矩阵的压缩存储实例
什么是稀疏矩阵呢,就是在M*N的矩阵中,有效值的个数远小于无效值的个数,并且这些数据的分布没有规律.在压缩存储稀疏矩阵的时候我们只存储极少数的有效数据.我们在这里使用三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后次序依次存放.下面我们来看一下代码实现. #include<iostream> #include<vector> #include<assert.h> using namespace std; template<class T> c
-
C++有限状态机实现计算器小程序
本文介绍利用有限状态机原理开发计算器小程序的过程. 实现的功能 支持整数.小数输入 支持+ - * / 四则运算 CE 清除当前操作数 C 清除所有.回到初始状态 回显操作数和结果 HSM状态图 计算器可以分为七种状态:Start.Operand_1.Negate_1.Operator.Operand_2.Negate_2.Error.其中Start.Operand_1.Operand_1状态又分了几种子状态. 下面简要的介绍下状态状态转换的过程: 启动软件,进入Start状态 当用户点击1-9
-
C++ 排序插入排序实例详解
排序--插入排序 插入排序的基本思想是每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止.常见的插入排序有插入排序(Insertion Sort),希尔排序(Shell Sort),二叉查找树排序(Tree Sort),图书馆排序(Library Sort),Patience排序(Patience Sort). 简单实例: #include <iostream> using namespace std; void InsertSort( i
-
C++ 中时间与时间戳的转换实例详解
C++ 中时间与时间戳的转换实例详解 // 设置时间显示格式: NSString *timeStr = @"2011-01-26 17:40:50"; NSDateFormatter *formatter = [[NSDateFormatter alloc] init]; [formatter setDateStyle:NSDateFormatterMediumStyle]; [formatter setTimeStyle:NSDateFormatterShortStyle]; [fo
-
C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)
C++ 数据结构二叉树(前序/中序/后序递归.非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子. 例: 实例代码: #include <iostream> #include <Windows.h> #include <stack> using namespace std; template <class T> struct BinaryTreeNode { int _data; BinaryTree
-
Java编程二项分布的递归和非递归实现代码实例
本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下. 问题来源: 算法第四版 第1.1节 习题27:return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); 计算递归调用次数,这里的递归式是怎么来的? 二项分布: 定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(n,p,k). 概率公式:P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k
-
数据结构 二叉树的递归与非递归
数据结构 二叉树的递归与非递归 实例代码: #include <iostream> #include <queue> #include <stack> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T
-
分析python动态规划的递归、非递归实现
概要 本文只是简单的介绍动态规划递归.非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大. [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 from functools import wraps def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) def wrapper(*args): if ar
-
java递归与非递归实现扫描文件夹下所有文件
java扫描指定文件夹下面的所有文件,供大家参考,具体内容如下 扫描一个文件夹下面的所有文件,因为文件夹的层数没有限制可能多达几十层几百层,通常会采用两种方式来遍历指定文件夹下面的所有文件. 递归方式 非递归方式(采用队列或者栈实现) 下面我就给出两种方式的实现代码,包括了递归与非递归实现,code如下所示. java代码: package q.test.filescanner; import java.io.File; import java.util.ArrayList; import ja
-
Java二叉树的四种遍历(递归和非递归)
二叉树的遍历可以分为前序.中序.后序.层次遍历. 前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中->左->右: 中序遍历,遍历节点的顺序为:左->中->右: 后序遍历,遍历节点的顺序为:左->右->中. 前序遍历 递归实现 public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q
-
java二叉树的几种遍历递归与非递归实现代码
前序(先序)遍历 中序遍历 后续遍历 层序遍历 如图二叉树: 二叉树结点结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } @Override public String toString(){ return "val: "+val; } } 访问函数 public void visit(TreeNode node){ System.out.print(
-
python如何实现递归转非递归
先说总结,这种方案总的来说就是机械化的强转,时间复杂度和空间复杂度没什么变化,唯二的优点可能是1. 不会爆栈,2. 节省了函数调用的开销 而且最终产出的代码效果不那么美观,比较冗长 思路是:当发生递归调用时,模拟函数调用的 压栈 .并处理 入参 和 返回值 和 记录返回到当前栈的时候该继续从哪里执行 以如下递归( leetcode爬楼梯 )为例 def f(n): if n <= 2: return n return f(n - 1) + f(n - 2) 第一步: 将涉及到递归调用的,单独变成
-
Java二叉树的四种遍历(递归与非递归)
目录 一.先序遍历与后序遍历 二.中序遍历 三.层序遍历 一.先序遍历与后序遍历 先序遍历根节点,再遍历左子树,再遍历右子树. 后序遍历先遍历左子树,再遍历右子树,再遍历根节点. 先序遍历递归实现: public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right); } 先序遍历的非递归
-
c语言排序之归并排序(递归和非递归)
目录 递归代码流程 非递归代码流程 两者比较 时间复杂度 代码(递归) 代码(非递归) 递归代码流程 归并就是把两个或多个序列合并,这里只介绍二路归并,就是不断的把序列分为2组,直到每个组有一个元素为止,然后再比较合并,直到合为1个序列,完成. 非递归代码流程 与递归不断分解数组相反,非递归直接从长度为1的子序列开始合并,直到全并为1个整个序列,复用了merge函数 两者比较 代码用非递归的方式效率更高一些: 空间复杂度:从O(log2n)变为1个临时数组O(n) 时间复杂度:少了递归的
随机推荐
- AngularJS自定义指令实现面包屑功能完整实例
- Shell 编程:Bash空格的那点事
- IE条件语句 IE hack大全
- Erlang程序设计(第2版)读书笔记:Erlang安装和基础语法
- 灵活实用VBS入门教程应用篇
- Xcode提高开发效率的代码块分享
- php获取本周开始日期和结束日期的方法
- JAVA使用Gson解析json数据实例解析
- iOS制作带弹跳动画发布界面
- PHP语法自动检查的Vim插件
- Go语言单链表实现方法
- XSLT轻松入门第三章:XSLT的元素语法
- jqurey+Jscex打造游戏力度条
- “禽兽”病毒(杀软终结者)的分析和手动解决方法图文第1/2页
- 微信小程序商品到详情的实现
- 在IE浏览器中resize事件执行多次的解决方法
- java 多线程-线程通信实例讲解
- 浅谈Java线程并发知识点
- Android嵌套滑动冲突的解决方法
- 微信小程序实现单选选项卡切换效果