算法基础(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; //当没有子节点的时候,或者不需要维护的时候跳出while
                swap(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!=right
    	m = (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;
          }
      };
      

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

视频汇聚平台EasyCVR安防视频监控平台新增角色权限功能分配的具体操作步骤

视频集中存储/云存储/安防视频监控/视频汇聚平台EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。 EasyCVR视频集中…

python连接PostgreSQL 数据库

执行如下命令安装 pip3 install psycopg2 python代码 Author: tkhywang 2810248865qq.com Date: 2023-08-21 11:42:17 LastEditors: tkhywang 2810248865qq.com LastEditTime: 2023-08-21 11:51:56 FilePath: \PythonProject02\PostgreSQL 数据库.py Description: 这是默认设置…

想解锁禁用的iPhone?除了可以使用电脑之外,这里还有不需要电脑的方法!

多次输入错误的密码后,iPhone将显示“iPhone已禁用”。这种情况看起来很棘手,因为你现在不能用iPhone做任何事情。对于这种情况,我们提供了几种有效的方法来帮助你在最棘手的问题中解锁禁用的iPhone。你可以选择使用或不使用电脑来解锁禁用的iPhone。 一、为什么你的iPhone…

深度学习实战49-基于卷积神经网络和注意力机制的汽车品牌与型号分类识别的应用

大家好,我是微学AI,今天给大家介绍一下深度学习实战49-基于卷积神经网络和注意力机制的汽车品牌与型号分类识别的应用,该项目就像是一只智慧而敏锐的眼睛,专注地凝视着汽车世界。这个项目使用PyTorch作为强有力的工具,提供了一个深度学习的舞台,让我们能够设计和训练一个…

穿起“新架构”的舞鞋,跳一支金融数字化转型的华尔兹

华尔兹&#xff0c;是男女两位舞者&#xff0c;通过形体的控制&#xff0c;舞步技巧的发挥&#xff0c;完美配合呈现而出的一种舞蹈形式。华尔兹舞姿&#xff0c;如行云流水、潇洒自如、飘逸优美&#xff0c;素有“舞中皇后”的美称。 在跳华尔兹的时候&#xff0c;如果舞者双…

会议剪影|思腾合力受邀参加2023中国算力大会并作主题演讲

共享数字经济合作新机遇&#xff0c;携手开创算力产业新未来。8月18日-19日&#xff0c;由工业和信息化部、宁夏回族自治区人民政府主办的2023中国算力大会、第二届“西部数谷”算力产业大会在银川盛大启幕。思腾云计算总经理庞志刚、思腾合力市场总监徐莉受邀参会。 ▲思腾云计…

客户案例:高性能、大规模、高可靠的AIGC承载网络

客户是一家AIGC领域的公司&#xff0c;他们通过构建一套完整的内容生产系统&#xff0c;革新内容创作过程&#xff0c;让用户以更低成本完成内容创作。 客户网络需求汇总 RoCE的计算网络RoCE存储网络1.不少于600端口200G以太网接入端口&#xff0c;未来可扩容至至少1280端口1.…

带你了解 Java 8 Stream:掌握流处理中的收集器技巧

Java 8 引入的 Stream 极大地简化了集合数据的处理&#xff0c;提供了一种现代、函数式的方式来处理数据。然而&#xff0c;在处理流时&#xff0c;我们经常需要将流的结果汇总到集合中或者进行各种统计计算。这就是收集器&#xff08;Collectors&#xff09;发挥作用的地方。本…

直播系统源码协议探索篇(二):网络套接字协议WebSocket

上一篇我们分析了直播平台的会话初始化协议SIP&#xff0c;他关乎着直播平台的实时通信和多方互动技术的实现&#xff0c;今天我们来讲另一个协议&#xff0c;叫网络套接字协议WebSocket&#xff0c;WebSocket基于TCP在客户端与服务器建立双向通信的网络协议&#xff0c;并且可…

React项目build打包后,页面空白的解决方案

问题描述&#xff1a; React项目执行 build 命令后&#xff0c;在本地服务器打开页面 是空白的&#xff0c;而且控制台报错 如下图所示 解决方法 打开根目录下的 package.json 文件&#xff0c;添加如下代码 {"name": "testproject","version"…

火山引擎发布自研视频编解码芯片 压缩效率提升30%

8月22日&#xff0c;火山引擎视频云宣布其自研的视频编解码芯片已成功出片。经验证&#xff0c;该芯片的视频压缩效率相比行业主流硬件编码器可提升30%以上&#xff0c;未来将服务于抖音、西瓜视频等视频业务&#xff0c;并将通过火山引擎视频云开放给企业客户。 火山引擎总裁…

vue3安装组件

如何创建vue项目链接&#xff1a;http://t.csdn.cn/tX8wY 新建vue项目如何配置&#xff1a;http://t.csdn.cn/YLdTG 我们这里拿vant组件演示 首先安装组件库 # Vue 3 项目&#xff0c;安装最新版 Vant npm i vant 可以在package.json查看 我们找到main.js 按钮举例 写入自…

微信小程序路由以及跳转页面传递参数

路由 在app.json的pages里面写 "pages/页面/页面" 直接保存pages直接生成非常方便 跳转页面 wx.navigateTo() 保留当前页面&#xff0c;跳转到应用内的某个非tabBar页面。 <text bindtap"daka">点击</text> daka:function () {wx.navigateTo…

关于chromedriver.exe一系列问题的解决办法

最新 chromedriver.exe下载地址&#xff1a;https://googlechromelabs.github.io/chrome-for-testing/#stable 下载最新版本的 chromedriver.exe 将其解压在 python.exe 同目录下&#xff0c;以及Chrome 的路径下 例如&#xff1a; C:\Program Files\Google\Chrome\Applicati…

校企合作 | 大势智慧受邀参与北斗共同体建设

8月16日&#xff0c;长江工业职业学院&#xff08;后简称“长江工院”&#xff09;副校长刘文胜&#xff0c;质管处处长黄世涛&#xff0c;测绘信息工程系党总支书记刘飞、系副主任陈志兰、系教师陈文玲一行莅临武汉大势智慧科技有限公司&#xff08;后简称“大势智慧”&#x…

ONLYOFFICE协作空间服务器如何一键安装自托管私有化部署

ONLYOFFICE协作空间服务器如何一键安装自托管私有化部署 如何在 Ubuntu 上部署 ONLYOFFICE 协作空间社区版&#xff1f;https://blog.csdn.net/m0_68274698/article/details/132069372?ops_request_misc&request_id&biz_id102&utm_termonlyoffice%20%E5%8D%8F%E4…

(动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】

❓ 剑指 Offer 42. 连续子数组的最大和 难度&#xff1a;简单 输入一个整型数组&#xff0c;数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为 O(n)。 示例1: 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1…

springMVC Unix 文件参数变更漏洞修复

错误信息如下&#xff1a; 解决方案&#xff1a; 原因&#xff1a;未对用户输入正确执行危险字符清理 未检查用户输入中是否包含“…”&#xff08;两个点&#xff09;字符串&#xff0c;比如 url 为 /login?action…/webapps/RTJEKSWTN26635&typerandomCode cookie为Coo…

ast在python架构中的使用

AST学习 AST简介&#xff1a; AST(Abstract syntac tree)是编译原理中的概念&#xff0c;是对源代码语法结构的一种抽象表示&#xff0c;它以树的形式表现编程语言的语法结构&#xff0c;树上的每个节点都表示源代码中的一种结构。 下面的代码展示了以demo.py中的ast语法&…

刷视频看到的联通流量卡广告,19元210G能买吗?

现在为了争夺客户资源&#xff0c;三大运营商纷纷发力&#xff0c;推出了各种优惠套餐&#xff0c;就比如&#xff1a;前段时间电信推出29元155G长期套餐&#xff0c;移动29元135G本地套餐&#xff0c;广电19元192G套餐。 当然&#xff0c;联通也是不甘示弱&#xff0c;也跟上…