C++ 中快排的递归和非递归实现

2024-12-03 01:17:25

快排的递归

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++有限状态机实现计算器小程序

本文介绍利用有限状态机原理开发计算器小程序的过程. 实现的功能支持整数.小数输入支持+ - * / 四则运算 CE 清除当前操作数 C 清除所有.回到初始状态回显操作数和结果 HSM状态图计算器可以分为七种状态:Start.Operand_1.Negate_1.Operator.Operand_2.Negate_2.Error.其中Start.Operand_1.Operand_1状态又分了几种子状态. 下面简要的介绍下状态状态转换的过程: 启动软件,进入Start状态当用户点击1-9
C++ 中时间与时间戳的转换实例详解

C++ 中时间与时间戳的转换实例详解 // 设置时间显示格式: NSString *timeStr = @"2011-01-26 17:40:50"; NSDateFormatter *formatter = [[NSDateFormatter alloc] init]; [formatter setDateStyle:NSDateFormatterMediumStyle]; [formatter setTimeStyle:NSDateFormatterShortStyle]; [fo
C++实现稀疏矩阵的压缩存储实例

什么是稀疏矩阵呢,就是在M*N的矩阵中,有效值的个数远小于无效值的个数,并且这些数据的分布没有规律.在压缩存储稀疏矩阵的时候我们只存储极少数的有效数据.我们在这里使用三元组存储每一个有效数据,三元组按原矩阵中的位置,以行优先级先后次序依次存放.下面我们来看一下代码实现. #include<iostream> #include<vector> #include<assert.h> using namespace std; template<class T> 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++ 排序插入排序实例详解

排序--插入排序插入排序的基本思想是每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止.常见的插入排序有插入排序(Insertion Sort),希尔排序(Shell Sort),二叉查找树排序(Tree Sort),图书馆排序(Library Sort),Patience排序(Patience Sort). 简单实例: #include <iostream> using namespace std; void InsertSort( i
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) 时间复杂度:少了递归的

C++ 中快排的递归和非递归实现

相关推荐

随机推荐