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;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(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) ​ 时间复杂度:少了递归的

随机推荐