算法基础(1):排序和查找算法

1、排序算法

在这里插入图片描述

1.1、堆排序(大顶堆)-重点:

  • 参考文章:堆排序1、堆排序二

  • 前置知识:

    • 大顶堆:完全二叉树,且父节点大于左右儿子,左右子树又是大顶堆,依赖数组来实现(vector)
    • 第一个节点的父节点:(i-1)/2,第i个节点的左儿子:i*2+1,第i个节点的右儿子:i*2+2,这里i从0开始;
    • 最后有儿子的节点:数组元素有n个,则最后一个有儿子的节点(n-1-1)/2=n/2-1
  • 堆排序基本思想:分为建堆排序两步,而核心步骤是对堆的属性进行维护

    • 维护堆:维护第i个节点的堆属性, 将该节点和左右儿子节点进行对比,选择大的进行交换,然后向下遍历,直到全部都满足堆的属性
    • 建堆:对已有的数组,从最后一个有儿子的节点开始向上遍历建立大顶堆,每次都需要维护节点的堆属性
    • 排序:每次将第一个元素和最后一个元素进行交换,每次交换,需要维护的数组长度-1,维护的节点是第一个节点
  • 复杂度:

    • 时间复杂度:最坏、最好、平均时间复杂度均为O(nlogn)
    • 空间复杂度O(1)
    • 描述是个不稳定的内部排序算法
  • 代码实现:实列测试

    class Solution {
    public:void heapify(vector<int>& nums,int n,int i) //维护第i个节点的堆结构{int largest = i;int left = i*2+1;//最多遍历树的高度,时间复杂度O(log n)while(left<n) //当left是最后一个节点,也还需要判断一次{if(left<n&&nums[largest]<nums[left]) largest = left; if(left+1<n&&nums[largest]<nums[left+1]) largest = left+1; //if(largest==i) break; //当没有子节点的时候,或者不需要维护的时候跳出whileswap(nums[largest],nums[i]); //将大的值放到i的位置上i = largest; //向下循环子节点left = i*2+1; //子节点的左儿子}}void heapSort(vector<int>& nums,int n){//建堆时间复杂度O(nlog n),从第一个有子节点的节点开始维护for(int i =n/2-1;i>=0;i--)         {heapify(nums,n,i); }for(int i=n-1;i>=0;i--) //堆排序 时间复杂度O(nlogn){ //每次将最后一个节点和第一个节点互换swap(nums[i],nums[0]);heapify(nums,i,0); //进行枝剪维护第0个节点}}vector<int> sortArray(vector<int>& nums) {heapSort(nums,nums.size());return nums;}
    };
    

1.2、快速排序-重点

  • 快速排序基本思想:在区间中,每次选择一个基点,小于基点的放在基点左边,大于基点的放在右边,分别对两边进行快速排序
  • 复杂度:
    • 时间复杂度:最好、平均时间复杂度为O(nlogn),最坏时间复杂度O(n^2)-序列基本有序,递归O(n)
    • 空间复杂度: 递归深度 O(log n)
    • 描述是个不稳定的内部排序
  • 代码实现:参考视频
    • 二路快排,普通快排

      class Solution {
      public:int partition(vector<int>& nums,int l,int r){int pivot = rand()%(r-l+1)+l;swap(nums[pivot],nums[r]);int i=l;for(int j=l;j<=r-1;j++) //用j遍历数组,{if(nums[j]<nums[r]){swap(nums[j],nums[i]);  //指针i始终指向pivot右边的第一个元素i++; //i前面的都是小于pivot的元素,}}//遍历完了,i依旧指向大于pivot的元素的第一位// j指向r的位置,也就是pivot的位置,只需要将pivot的位置和i的位置进行交换即可swap(nums[r],nums[i]);return i;}void quikSort(vector<int>& nums,int left,int right){if(left>=right) return;int mid = partition(nums,left,right);quikSort(nums,left,mid-1);quikSort(nums,mid+1,right);}vector<int> sortArray(vector<int>& nums) {quikSort(nums,0,nums.size()-1);return nums;}
      };
      
    • 三路快排,用于重复元素多的情况

      class Solution {
      public:vector<int> partition(vector<int>& nums,int l,int r){int pivot = rand()%(r-l+1)+l;swap(nums[pivot],nums[r]);// 三路快排,p指向pivot元素相同的第一个元素// i指向大于pivot的元素的第一个位置int i=l;int p=l;for(int j=l;j<=r-1;j++){if(nums[j]<nums[r]){swap(nums[j],nums[i]);swap(nums[i],nums[p]);i++; p++;}else if(nums[j]==nums[r]){swap(nums[j],nums[i]);i++;}}swap(nums[r],nums[i]);return vector<int>{p,i};}void quikSort(vector<int>& nums,int left,int right){if(left>=right) return;vector<int> v = partition(nums,left,right);quikSort(nums,left,v[0]-1);quikSort(nums,v[1]+1,right);}vector<int> sortArray(vector<int>& nums) {quikSort(nums,0,nums.size()-1);return nums;}
      };
      

1.3、归并排序-重点

  • 归并排序基本思想:分治的思想,每将数组递归分成长度接近的两个部分,再进行排序合并回溯
  • 复杂度
    • 时间复杂度:平均、最好、最坏均为O(nlogn)
    • 空间复杂度:需要引入辅助空间O(n),如果是给链表排序则只需要O(1)
    • 描述:是个稳定的外部排序算法
  • 代码实现:
    • 数组归并
    class Solution {
    public:void merge(vector<int>&nums,vector<int>& arr,int left,int mid,int right){int l = left;//左边第一个未排序元素int r = mid+1;//右边第一个未排序元素int pos = left;//arr数组// 合并while(l<=mid&&r<=right){if(nums[l]<nums[r]) arr[pos++] = nums[l++];else arr[pos++] = nums[r++];}//合并剩余元素while(l<=mid) arr[pos++] = nums[l++];while(r<=right) arr[pos++] = nums[r++];//将临时数组进行拷贝while(left<=right){nums[left] = arr[left];left++;}}void mergeSort(vector<int>& nums,vector<int>& arr,int left,int right){ if(left>=right) return;int mid = (right+left)/2;mergeSort(nums,arr,left,mid);mergeSort(nums,arr,mid+1,right);merge(nums,arr,left,mid,right);}vector<int> sortArray(vector<int>& nums) {vector<int> arr(nums.size());mergeSort(nums,arr,0,nums.size()-1);return nums;}
    };
    
    • 链表归并:

1.4、冒泡排序

  • 冒泡排序基本思想:每次循环将最大元素交换到最右边,每次内部循环都需要交换

  • 和选择排序的区别:异曲同工,选择排序交换次数少,但是在数组有序的情况下,依旧需要完整的遍历完,时间复杂度稳定到O(n^2),冒泡排序,可以在数组有序的情况下提前结束

  • 复杂度:

    • 时间复杂度:平均时间复杂度O(n^2),最好时间复杂度O(n),平均时间复杂度O(n^2) - 空间复杂度:O(1)
    • 描述:是个稳定的内部排序
  • 代码实现:

    // 简单版本,和选择排序基本一致
    class Solution {
    public:void bubbleSort(vector<int>& nums,int n){for(int i=nums.size()-1;i>=0;i--){for(int j=0;j<i;++j){if(nums[j]>nums[j+1]) swap(nums[j],nums[j+1]);}}}vector<int> sortArray(vector<int>& nums) {bubbleSort(nums,nums.size());return nums;}
    };
    // 优化版本class Solution {public:void bubbleSort(vector<int>& nums,int n){bool flag = false;for(int i=nums.size()-1;i>=0;i--){flag = false;for(int j=0;j<i;++j) //一般过去是有序的,则时间复杂度只有O(n){if(nums[j]>nums[j+1]){swap(nums[j],nums[j+1]);flag = true;}}if(!flag) break;}}vector<int> sortArray(vector<int>& nums) {bubbleSort(nums,nums.size());return nums;}};
    

1.5、选择排序

  • 选择排序基本思想:每次选择一个最大的元素排到后面,每次内部循环只需要交换一次

  • 复杂度:

    • 时间复杂度:最好、最坏、平均时间复杂度为O(n^2)
    • 空间复杂度:没有辅助容器为O(1)
    • 描述:是个不稳定的内部排序
  • 代码实现:

    class Solution {
    public:void selectSort(vector<int>& nums,int n){int Max=-1;for(int i=nums.size()-1;i>=0;i--){Max = i;for(int j=0;j<i;++j){if(nums[j]>nums[Max]) Max=j;}swap(nums[i],nums[Max]);}}vector<int> sortArray(vector<int>& nums) {selectSort(nums,nums.size());return nums;}
    };
    

1.6、插入排序

  • 插入排序基本思想:每次将一个元素插入到前面维护好顺序的元素里面

  • 复杂度:

    • 时间复杂度:最坏、平均为O(n^2),最好为O(n)-基本有序的情况
    • 空间复杂度:O(1)
    • 描述:是个稳定的内部排序算法
  • 代码实现:

    class Solution {
    public:void InsertSort(vector<int>& nums,int n){for(int i=1;i<n;++i){// 每次将第i个元素插入到前i-1数组中int tmp = nums[i]; int j=i;while(j>0 && nums[j-1]>tmp){nums[j] = nums[j-1];--j;}nums[j] = tmp;}}vector<int> sortArray(vector<int>& nums) {InsertSort(nums,nums.size());return nums;}
    };
    

2、查找算法

2.1、二分查找

  • 基本思想:前提是数组有序,通过中间点折半的思想实现快速的查找

  • 红蓝边界思想:

    int left = -1,right = N; // 数组下标从0到N-1
    while left+1!=rightm = (left+right)/2;if IsBlue(m)left = m;else right = m;
    return left or right;  //返回值根据题目要求来定
    
  • 复杂度:

    • 时间复杂度:O(log n)
  • 代码实现:

    • 在有序数组中查找元素的下标:测试实列

      class Solution {
      public:/*红蓝边界求值,时间复杂度O(log n)1.没有这个元素的话,且right进行了移动2.没有这个元素的话,且right没有进行移动3.有这个元素,直接返回right*/int search(vector<int>& nums, int target) {int left = -1;int right = nums.size();while(left+1!=right){int mid = (left+right)/2;if(nums[mid]<target) left = mid;else right = mid;}//需要判断对应的节点不存在的可能if(right==nums.size()||nums[right]!=target) return -1; else return right;}
      };
      

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/100530.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QT中按钮的基类QAbstractButton

QT中按钮的基类QAbstractButton 关于控件类的学习方法继承关系信号槽函数标题和图标按钮的 Check 属性 关于控件类的学习方法 控件类很多&#xff0c;API更多&#xff0c;但是不需要记忆知道控件对应的类名&#xff0c;通过帮助文档随用随查优先看帮助文档中控件对应的信号和槽…

LeetCode算法心得——k-avoiding 数组的最小总和(标记数组)

大家好&#xff0c;我是晴天学长&#xff0c;这是一个细节题和一部分的思维题哈&#xff01; 2) .算法思路 k-avoiding 数组的最小总和 1,填充一个1到n 的Boolean的数组 要n个数&#xff0c;但是数组大小不能确定。 所以建立1000的大小。 2.遍历筛选&#xff0c;如果数组中有这…

ubuntu18.04安装远程控制软件ToDest方法,针对官网指令报错情况

有时我们在家办公&#xff0c;需要控制实验室的笔记本&#xff0c;因此好用的远程控制软件会让我们的工作事半功倍&#xff01; 常用的远程控制软件有ToDesk&#xff0c;向日葵&#xff0c;以及TeamViewer&#xff0c;但是为感觉ToDesk更流畅一些&#xff0c;所以这里介绍一下…

MySQL之索引和事务

索引什么是索引索引怎么用索引的原理 事务使用事务事务特性MySQL隔离级别 索引 什么是索引 索引包含数据表所有记录的引用指针&#xff1b;你可以对某一列或者多列创建索引和指定不同的类型&#xff08;唯一索引、主键索引、普通索引等不同类型&#xff1b;他们底层实现也是不…

Linux的基础指令

目录 1、ls指令 .和..意义 2、pwd指令 3、cd指令 ①cd ~ ②cd - 关于cd ..的用法 绝对路径和相对路径 4、touch指令 5、mkdir指令 tree指令 6、rmdir指令 7、rm指令 * 8、man指令 9、cp指令 nano&#xff1a; 10、mv指令 11、cat指令 12、more指令 13、less…

3d max省时插件CG MAGIC功能中的材质参数可一键优化!

渲染的最终结果就是为了让渲染效果更加真实的体现。 对于一些操作上&#xff0c;可能还是费些时间&#xff0c;VRay可以说是在给材质做加法的路上越走越远&#xff0c;透明度、凹凸、反射等等参数细节越做越多。 对于材质参数调节的重要性大家都心里有数的。 VRay材质系统的每…

万能的Python爬虫模板来了

目录 万能爬虫组成部分 示例代码 注意事项 总结 Python爬虫是一种强大的工具&#xff0c;可以帮助我们自动化地从网页中获取数据。无论是获取最新的新闻、实时的股票数据&#xff0c;还是进行网络数据分析&#xff0c;Python爬虫都能发挥重要作用。今天介绍一个万能python爬…

laravel aws s3

由于公司有境外项目&#xff0c;服务器、文件存储都是用的亚马逊&#xff0c;真真地是没有用过&#xff0c;在此记录一下自己的s3研究结果 Laravel - aws - s3 第一步创建用户&#xff0c;生成秘钥&#xff1a; 第二步创建存储桶&#xff1a; 1、创建存储桶时&#xff0c;以下…

思腾云计算

去年世界人工智能大会&#xff08;WAIC 2022&#xff09;上&#xff0c;只有屈指可数的几家大厂推出大模型&#xff0c;但在科技部新一代人工智能发展研究中心5月底发布的《中国人工智能大模型地图研究报告》显示&#xff0c;我国10亿参数规模以上的大模型已发布79个&#xff0…

redis数据类型详解+实例

redis中的数据类型&#xff1a; string&#xff0c;list, set, zset, hash,bitmaps, hyperloglog, gepspatial 目录 一、 String 二、List 三、Set 四、Zset 五、Hash 六、Bitmaps 七、Hyperloglog 八、Gepspatial 一、 String redis最基本的数据类型&#xff0c;一个…

wifi高通驱动之WCNSS_qcom_cfg.ini以及MCS、空间流数的学习和记录

一、WCNSS_qcom_cfg.ini 这个文件说是可以调优wifi的带宽&#xff0c;还有MIMO技术 Android Wi-Fi MIMO/SISO设置方法&#xff08;基于高通平台&#xff09;_广凯的博客-CSDN博客 不是太了解&#xff0c;先记录一下&#xff0c;个人感觉MCS和MIMO技术最全的应该是下面的网址…

使用ChatGPT-4优化编程效率:高效查询代码示例和解决方案

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…

Web Components

Web Components标准非常重要的一个特性是&#xff0c;它使开发者能够将HTML页面的功能封装为custom elements&#xff08;自定义标签&#xff09;&#xff0c;可以使用CustomElementRegistry来管理自定义标签 <script>//1、创建自定义标签class NewElement extends HTML…

FastDFS与Nginx结合搭建文件服务器,并实现公网访问【内网穿透】

文章目录 前言1. 本地搭建FastDFS文件系统1.1 环境安装1.2 安装libfastcommon1.3 安装FastDFS1.4 配置Tracker1.5 配置Storage1.6 测试上传下载1.7 与Nginx整合1.8 安装Nginx1.9 配置Nginx 2. 局域网测试访问FastDFS3. 安装cpolar内网穿透4. 配置公网访问地址5. 固定公网地址5.…

分布式基础

1、分布式简介 1.1、分布式定义 分布式系统是一个硬件或软件组件分布在不同的网络计算机上&#xff0c;彼此之间仅仅通过消息传递进行通信和协调的系统。 1.2、分布式特点 分布性&#xff1a;分布式系统中的多台计算机都会在空间上随意分布&#xff0c;同时&#xff0c;机器…

最新ai系统ChatGPT程序源码+详细搭建教程+mj以图生图+Dall-E2绘画+支持GPT4+AI绘画+H5端+Prompt知识库

目录 一、前言 二、系统演示 三、功能模块 3.1 GPT模型提问 3.2 应用工作台 3.3 Midjourney专业绘画 3.4 mind思维导图 四、源码系统 4.1 前台演示站点 4.2 SparkAi源码下载 4.3 SparkAi系统文档 五、详细搭建教程 5.1 基础env环境配置 5.2 env.env文件配置 六、环境…

HAProxy的配置与搭建

Haproxy概念 HAProxy是可提供高可用性、负载均衡以及基于TCP和HTTP应用的代理&#xff0c;是免费、快速并且可靠的一种解决方案。HAProxy非常适用于并发大&#xff08;并发量达1w以上&#xff09;web站点&#xff0c;这些站点通常又需要会话保持或七层处理。HAProxy的运行模式…

C++信息学奥赛1119:矩阵交换行

解题思路&#xff1a;当输出时换行 解题程序&#xff1a; #include<iostream> using namespace std; int main() {int arr[5][5];// 输入矩阵元素for(int i0;i<5;i){for(int j0;j<5;j){cin>>arr[i][j];}} int n,m;cin>>n>>m;// 根据条件进行矩…

Qt 屏幕偶发性失灵

项目场景: 基于NXP i.mx7的Qt应用层项目开发,通过goodix使用触摸屏,走i2c协议。 问题描述 触摸屏使用过程中意外卡死,现场分为多种: i2c总线传输错误,直观表现为触摸屏无效,任何与触摸屏挂接在同一总线上的i2c设备,均受到干扰,并且在传输过程中内核报错以下代码: G…

【C语言】字符串和内存函数的介绍 -- 详解

重点介绍处理字符和字符串的库函数的使用和注意事项。 C语言中对字符和字符串的处理很是频繁&#xff0c;但是C语言本身是没有字符串类型的&#xff0c;字符串通常放在常量字符串中或者字符数组中。字符串常量适用于那些对它不做修改的字符串函数。 一、求字符串长度⚪strlen …