首页 > 编程语言 >常见算法模板

常见算法模板

时间:2024-03-22 22:11:27浏览次数:34  
标签:sort right int 常见 mid merge 算法 模板 left

常见算法

快速排序

#include <iostream>
#include <algorithm>
//快速排序
void qsort(int a[],int left,int right)
{
if(left>=right)return ;
int i=left-1,j=right+1;
int x=a[left+right >>1];
while(i<j)
{
do i++;while(a[i]<x);
do j--;while(a[j]>x);
if(i<j)
{
int t=a[i];a[i]=a[j];a[j]=t;
}
}
qsort(a,left,j);
qsort(a,j+1,right);
}
using namespace std;
int main()
{
int arr[10]={2,3,4,5,6,7,8,9,1};
auto show=[&](int arr[10]){
for(int i=0;i<10;++i)
cout<<arr[i]<<' ';
cout<<endl;
};
show(arr);
qsort(arr,0,9);
show(arr);
return 0;
}

归并排序

#include <iostream>

void merge_sort(int q[], int l, int r) {
  if (l >= r) return;

  int mid = l + r >> 1;
  merge_sort(q, l, mid);
  merge_sort(q, mid + 1, r);

  int k = 0, i = l, j = mid + 1;
  int tmp[r - l + 1];  // 临时数组

  while (i <= mid && j <= r)  
    if (q[i] <= q[j])  
      tmp[k++] = q[i++];
     else
      tmp[k++] = q[j++];
	  
  while (i <= mid)
    tmp[k++] = q[i++];
	
  while (j <= r) 
    tmp[k++] = q[j++];

  for (i = l, j = 0; i <= r; i++, j++)
    q[i] = tmp[j];
}
int main() {
  int arr[] = {5, 2, 4, 6, 1, 3};
  int n = sizeof(arr) / sizeof(arr[0]);
  merge_sort(arr, 0, n - 1);
  for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
  return 0;
}

标签:sort,right,int,常见,mid,merge,算法,模板,left
From: https://www.cnblogs.com/AndreaDO/p/18089814

相关文章

  • 是否具有环境感知能力是人形机器人的基本要求 —— 基于感知的运动控制算法
    智能机器人与传统机器人的区别在于是否具有智能决策模块,直白的说就是在于是否使用强化学习算法进行动作的智能决策。但是,并不是使用强化学习算法的机器人就是智能机器人,尤其是人形机器人。强化学习算法是需要对环境进行感知的,这其实还可以分为两类,第一类是比较理想下的设定,就是指......
  • 算法Day1—动态规划(剑指offer42+47)
    动态规划解题思路确定状态(两个核心,最后一步,化成子问题)根据最后一步,往前推。然后将问题转化成从开始到最后一步的子问题。状态转移方程结果=开始到最后一步+最后一步。开始和边界条件确定0,以及边界不适合转移方程的条件。计算顺序一般都是推导到从最开始计算。剑......
  • 算法Day2—动态规划(剑指offer63+01背包问题(1))
    剑指offer63:股票的最大利润题目:假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?转移方程:dp[i]=max(dp[i−1],第i日卖出的最大利润中的最大值)classSolution{publicintmaxProfit(int[]prices){intcost=......
  • 字符串与BF算法
    1.定义:BF算法,即暴力(BruteForce)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。2.BF......
  • 【C++ 08】vector 顺序表的常见基本操作
    文章目录前言......
  • 算法打卡day25|回溯法篇05|Leetcode 491.递增子序列、46.全排列、47.全排列 II
     算法题Leetcode491.递增子序列题目链接:491.递增子序列大佬视频讲解:递增子序列视频讲解 个人思路和昨天的子集2有点像,但昨天的题是通过排序,再加一个标记数组来达到去重的目的。而本题求自增子序列,是不能对原数组进行排序的,因为排完序的数组都是自增子序列了。解决......
  • 机器人路径规划:基于霸王龙优化算法(Tyrannosaurus optimization,TROA)的机器人路径规划(提
     一、机器人路径规划介绍移动机器人(Mobilerobot,MR)的路径规划是移动机器人研究的重要分支之,是对其进行控制的基础。根据环境信息的已知程度不同,路径规划分为基于环境信息已知的全局路径规划和基于环境信息未知或局部已知的局部路径规划。随着科技的快速发展以及机器人的大量......
  • 代码随想录算法训练营第五十四天| ● 392.判断子序列 ● 115.不同的子序列
    判断子序列 题目链接:392.判断子序列-力扣(LeetCode)思路:从子串s开始遍历,查找t中是否存在,因为全程不需要回溯,因此两个for循环就解决了。只是要注意return的时机。(只要不想写的很简洁,逻辑挺简单的其实)classSolution{public:boolisSubsequence(strings,stringt){......
  • [C++提高编程](一):模板----函数模板
    目录函数模板作用函数模板的语法注意事项普通函数与函数模板的区别普通函数与函数模板的调用规则模板的局限性案例--通用数组选择排序从大到小模板是C++中泛型编程的基础,一个模板就是一个创建类或函数的蓝图或者公式。函数模板作用建立一个通用函数,其函数返回值类型......
  • 常见优化器对比:梯度下降法、带动量的梯度下降法、Adagrad、RMSProp、Adam
    系列文章目录李沐《动手学深度学习》线性神经网络线性回归李沐《动手学深度学习》优化算法(相关概念、梯度下降法、牛顿法)李沐《动手学深度学习》优化算法(经典优化算法)文章目录系列文章目录一、梯度下降法(一)基本思想(二)梯度下降法的三种不同形式(三)优缺点二、带动量的......