数据结构排序算法总结

news/2024/2/23 16:16:54/文章来源:https://blog.csdn.net/weixin_44340277/article/details/135530561

直接插入排序 + 折半插入排序 + 希尔排序

冒泡排序 + 快速排序

选择排序 + 堆排序

归并排序

1.直接插入排序

前面的有序 后面的无序,无序元素插入到前面的有序列表中

        int len = nums.length, i = 1, j = 0;for(i=1; i<len; i++){int ele = nums[i];// 插入过程for(j = i-1; j >= 0 && nums[j] > ele; j--)nums[j+1] = nums[j];nums[j+1] = ele;}return nums;

最坏时间复杂度O(n^2),最好时间复杂度O(n),空间复杂度O(1),稳定排序

2.折半插入排序:

折半插入排序可以拆分为 折半查找插入位置 + 数组插入

具体折半查找过程 内部的细节总结 折半查找过程-CSDN博客

        int i, j, ele, m, low, high, len = nums.length;for (i = 1; i < len; i++){ele = nums[i];// 折半查找low = 0; high = i-1;while (low <= high){m = (low +high) / 2;if(nums[m] > ele)high = m-1;elselow = m+1;}// 排序for (j = i-1; j>=low; j--)nums[j+1] = nums[j];nums[j+1] = ele;}return nums;

最坏时间复杂度O(n^2),最好时间复杂度O(n\log n),空间复杂度O(1),稳定排序.

3.冒泡排序:

        // 外层循环控制趟数for (int i = 0; i < n - 1; i++) {flag =false;// 内层循环进行比较和交换for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr[j], arr[j+1]);flag = true;}}}

最坏时间复杂度O(n^2),最好时间复杂度O(n),空间复杂度O(1),稳定排序.

4.快速排序:

    public int partition(int[] nums, int left, int right){int pivot = nums[left];while(left < right){while(left < right && pivot <= nums[right]) right--;nums[left] = nums[right];while(left < right && pivot >= nums[left])left++;nums[right] = nums[left];}nums[left] = pivot;return left;}
    public void quickSort(int[] nums, int left, int right){if(left < right){int partition = partition(nums, left, right);quickSort(nums, left, partition-1);quickSort(nums, partition+1, right);}}

最坏时间复杂度O(n^2),最好时间复杂度O(n\log n),空间复杂度O(n\log n),不稳定排序.

每一次确定一个点的最终位置,然后把整个数组划分两部分。形成递归树,最坏情况是树高=n,且每一层都要遍历一次数组。 空间复杂度就是整个递归树。

可参考快速排序最好,最坏,平均复杂度分析_对n个记录进行快速排序,在最坏的情况下,其时间复杂度是-CSDN博客

5.选择排序

    public void selectSort(int[] nums){for(int i=0; i<nums.length; i++){int index = i;int min = nums[i];for(int j=i; j<nums.length; j++){index = nums[j] < min ? j:index;min = nums[j] < min ? nums[j] : min;}nums[index] = nums[i];nums[i] = min;}}

最坏时间复杂度O(n^2),最好时间复杂度O(n^2),空间复杂度O(1),不稳定排序

6.堆排序

分为建堆,调整,排序。

建堆build_heap:  len/2的位置往前遍历 adjust每一个节点。

    public void buildHeap(int[] nums, int len){for(int i=(len)/2; i>0; i--){adjust(nums, i, len);}}

调整adjust:  for遍历子节点,顶点往下传。

    public void adjust(int[] nums, int k, int len){int val = nums[k];for(int i=2*k; i<=len; i=i*2){if(i+1 <= len && nums[i+1] > nums[i])i = i+1;if(nums[i] > val){nums[k] = nums[i];k = i;}elsebreak;}nums[k] = val;}

整合 堆排序 heap_sort

    public void heapSort(int[] nums, int len){buildHeap(nums, len);for(int i=len; i>1; i--){swap(nums,1,i);adjust(nums,1,i-1);}}

最坏时间复杂度O(n\log n),最好时间复杂度O(n\log n),空间复杂度O(1),不稳定排序.

7.归并排序

把两个有序的子数组 合并为一个 大的有序数组。

merge 合并函数

    public void merge(int[] nums, int left, int mid, int right){int[] arr = new int[right-left+1];for(int i=0; i<arr.length; i++){arr[i] = nums[left+i];}int i = 0;int j = mid-left+1;int k = left;while(i <= mid-left && j <= right-left && k <= right){if(arr[i] <= arr[j])nums[k++] = arr[i++];elsenums[k++] = arr[j++];}while(i <= mid-left) nums[k++] = arr[i++];while(j <= right-left)nums[k++] = arr[j++];}

递归 拆分数组

    public void mergeSort(int[] nums, int left, int right){if(left < right){int mid = (left + right) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid+1, right);merge(nums,left, mid, right);}}

最坏时间复杂度O(n\log n),最好时间复杂度O(n\log n),空间复杂度O(n),稳定排序.

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

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

相关文章

【上分日记】第379场周赛(分类讨论 + 数学 + 前缀和)

文章目录 前言正文1.3000. 对角线最长的矩形的面积2.3001. 捕获黑皇后需要的最少移动次数3.3002. 移除后集合的最多元素数3.3003. 执行操作后的最大分割数量 总结尾序 前言 终于考完试了&#xff0c;考了四天&#xff0c;也耽搁了四天&#xff0c;这就赶紧来补这场周赛的题了&a…

gitee完整使用教程,创建项目并上传

目录 一 什么是gitee 二 安装Git 三 登录gitee&#xff0c;生成密钥 四 配置SSH密钥 五 创建项目 六 克隆仓库到本地 七 关联本地工程到远程仓库 八 添加文件 九 异常处理 十 删除仓储 十一 git常用命令 一 什么是gitee gitee是开源中国推出的基于git的代码托管服务…

3种ffmpeg-web端视频直播推流方案

ffmpeg-web端视频直播推流方案 记录了三种 ffmpeg 工具进行推流的方法&#xff0c;并在web端实现直播效果。 一. node-media-server ffmpeg 推流rtmp 安装node-media-server依赖,新建app.js运行 npm install node-media-server -g const NodeMediaServer require(node-…

e2studio开发三轴加速度计LIS2DW12(4)----测量倾斜度

e2studio开发三轴加速度计LIS2DW12.4--测量倾斜度 概述视频教学样品申请源码下载计算倾斜角度工作原理单轴倾斜检测双轴倾斜检测三轴倾斜检测通信模式管脚定义IIC通信模式速率新建工程工程模板保存工程路径芯片配置工程模板选择时钟设置UART配置UART属性配置设置e2studio堆栈e…

004 Golang-channel-practice 左右括号匹配

第四题 左右括号打印 一个协程负责打印“&#xff08;”&#xff0c;一个协程负责打印“&#xff09;”&#xff0c;左右括号的数量要匹配。在这道题目里&#xff0c;我在main函数里进行了一个死循环。会产生一个随机数&#xff0c;随机数就是接下来要打印的左括号的数量。 例…

spring boot mybatis plus mapper如何自动注册到spring bean容器

##Import(AutoConfiguredMapperScannerRegistrar.class) ##注册MapperScannerConfigurer ##MapperScannerConfigurer.postProcessBeanDefinitionRegistry方法扫描注册mapper ##找到mapper候选者 ##过滤mapper 类 候选者 ##BeanDefinitionHolder注册到spring 容器

竞赛保研 基于深度学习的动物识别 - 卷积神经网络 机器视觉 图像识别

文章目录 0 前言1 背景2 算法原理2.1 动物识别方法概况2.2 常用的网络模型2.2.1 B-CNN2.2.2 SSD 3 SSD动物目标检测流程4 实现效果5 部分相关代码5.1 数据预处理5.2 构建卷积神经网络5.3 tensorflow计算图可视化5.4 网络模型训练5.5 对猫狗图像进行2分类 6 最后 0 前言 &#…

c++泛型算法相关笔记

一. 泛型算法 1. 前言 泛型算法&#xff1a;可以支持多种类型的算法 此处主要来讨论怎么使用标准库中定义的泛型算法<algorithm>, numeric, ranges. 在引入泛型算法之前&#xff0c;还有一种是方法的形式&#xff0c;比如说std::sort 和std::list::sort&#xff0c;前者…

微信小程序上传并显示图片

实现效果&#xff1a; 上传前显示&#xff1a; 点击后可上传&#xff0c;上传后显示&#xff1a; 源代码&#xff1a; .wxml <view class"{{company_logo_src?blank-area:}}" style"position:absolute;top:30rpx;right:30rpx;height:100rpx;width:100rp…

力扣67. 二进制求和算法

一、【写在前面】 这道题需要&#xff0c;给你两个字符串比如 a "1010", b "1011"答案是&#xff1a;"10101" 然后需要你给出计算结果&#xff0c;那么我们很容易想到两种做法 1. 调库做法&#xff1a;直接转化为整数&#xff0c;然后用内…

在CentOS上设置和管理静态HTTP网站的版本控制

在CentOS上设置和管理静态HTTP网站的版本控制是一项重要的任务&#xff0c;它可以帮助您跟踪和回滚对网站所做的更改&#xff0c;确保数据的一致性和完整性。以下是在CentOS上设置和管理静态HTTP网站的版本控制的步骤&#xff1a; 安装版本控制系统在CentOS上安装Git或其他版本…

K8S--Ingress的作用

原文网址&#xff1a;K8S--Ingress的作用-CSDN博客 简介 本文介绍K8S的Ingress的作用。 ----------------------------------------------------------------------------------------------- 分享Java真实高频面试题&#xff0c;吊打面试官&#xff1a; Java后端真实面试题…

[后端] 微服务的前世今生

微服务的前世今生 整体脉络: 单体 -> 垂直划分 -> SOA -> micro service 微服务 -> services mesh服务网格 -> future 文章目录 微服务的前世今生单一应用架构特征优点&#xff1a;缺点&#xff1a; 垂直应用架构特征优点缺点 SOA 面向服务架构特征优点缺点 微服…

STM32快速复制MX25L1606E系列Flash

去年做了一个使用RS485对PIC18F45K80系列单片机进行在线升级的程序&#xff0c;如果是小批量的出厂烧录程序和升级验证&#xff08;出厂前肯定要测试单片机是否能正常读写Flash&#xff09;是可以的&#xff0c;但是后来产品订单量很大&#xff0c;生产线的烧录及升级验证就很缓…

Android Retrofit使用详情

一、 Retrofit是什么 Retrofit是Android用来接口请求的网络框架&#xff0c;内部是基于OkHttp实现的&#xff0c;retrofit负责接口请求的封装&#xff0c;retrofit可以直接将接口数据解析为Bean类、List集合等&#xff0c;直接简化了中间繁琐的数据解析过程 二、 Retrofit的简单…

使用 Apache POI 更新/覆盖 特定的单元格

使用 Apache POI 更新特定的单元格 一. 需求二. 实现三. 效果 一. 需求 将以下表中第4行&#xff0c;第4列的单元格由“张宇”更新为“汤家凤”&#xff0c;并将更行后的结果写入新的Excel文件中&#xff1b; 二. 实现 使用Apache POI&#xff0c;可以精确定位到需要更改的单…

stm32学习笔记:USART串口通信

1、串口通信协议&#xff08;简介软硬件规则&#xff09; 全双工&#xff1a;打电话。半双工&#xff1a;对讲机。单工&#xff1a;广播 时钟&#xff1a;I2C和SPI有单独的时钟线&#xff0c;所以它们是同步的&#xff0c;接收方可以在时钟信号的指引下进行采样。串口、CAN和…

Picturesocial | 开发实践:如何在15分钟内将应用容器化

在常见的软件架构体系中&#xff0c;容器无疑是一个技术热点。有些开发者在工作中熟练使用容器技术&#xff0c;有些可能刚刚开始容器之旅。 面对容器使用经验不同的各类开发者&#xff0c;我们希望通过这个系列文章&#xff0c;由浅入深地介绍如何使用容器技术来构建&#xf…

C语言天花板——指针(经典题目)

指针我们已经学习的差不多了&#xff0c;今天我来给大家分享几个经典的题目&#xff0c;来让我们相互学习&#x1f3ce;️&#x1f3ce;️&#x1f3ce;️ int main() {int a[4] { 1, 2, 3, 4 };int* ptr1 (int*)(&a 1);int* ptr2 (int*)((int)a 1);printf("%x,%…

C++ OJ基础

C OJ基础 在学校学习C程序设计基础课程的OJ题目 缺少第二十题 这里写目录标题 C OJ基础习题练习(一)打印图形习题练习(二)数据的输入输出习题练习(三)函数重载习题练习(四)设计矩形类习题练习(五)定义Tree类习题练习(六)完善职工工资类Salary的设计习题练习(七)设计矩形类recta…