数据结构与算法:排序算法(1)
目录
冒泡排序
思想
代码实现
优化
鸡尾酒排序
优缺点
适用场景
快速排序
介绍
流程
基准元素选择
元素交换
1.双边循环法
使用流程
代码实现
2.单边循环法
使用流程
代码实现
3.非递归实现
排序在生活中无处不在,看似简单,背后却隐藏着多种多样的算法和思想;
根据时间复杂度的不同,主流的排序算法可以分为三大类:
1.时间复杂度为O(n^2)的排序算法
冒泡排序
选择排序
插入排序
希尔排序
2.时间复杂度为O(nlogn)的排序算法
快速排序
归并排序
堆排序
3.时间复杂度为线性的排序算法
计数排序
桶排序
基数排序
根据稳定性:稳定排序、不稳定排序(如果值相同的元素在排序后仍然保持着排序前的顺序,则这样的排序算法是稳定排序;如果值相同的元素在排序后打乱了排序前的顺序,则这样的排序算法是
不稳定排序)
冒泡排序
冒泡排序,是一种基础的交换排序;这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点地向着数组的一侧移动
思想
把相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧相邻元素时,位置不变
元素9作为数列中最大的元素,就像是汽水里的小气泡一样,“漂”到了最右侧;再经过多轮排序,所有元素都是有序的。
冒泡排序是一种稳定排序,值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素,总共遍历(元素数量-1)轮,所以平均时间复杂度是O(n^2);
代码实现
public static void main(String[] args){int[] array = new int[]{5,8,6,3,9,2,1,7};bubbleSort(array);System.out.println(Arrays.toString(array));}public static void bubbleSort(int array[]){for(int i = 0; i < array.length - 1; i++){for(int j = 0; j < array.length - i - 1; j++){int tmp = 0;if(array[j] > array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;}}}}
使用双循环进行排序。外部循环控制所有的回合,内部循环实现每一轮的冒泡处理,先进行元素比较,再进行元素交换
优化
利用布尔变量作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,则说明数列已然有序,然后直接跳出大循环
public static void bubbleSort(int array[]){for(int i = 0; i < array.length - 1; i++){boolean isSorted = true;for(int j = 0; j < array.length - i - 1; j++){int tmp = 0;if(array[j] > array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;isSorted = false;}}if(isSorted){break;}}}
鸡尾酒排序
鸡尾酒排序的元素比较和交换过程是双向的;排序过程就像钟摆一样,第1轮从左到右,第2轮从右到左,第3轮再从左到右……
public static void main(String[] args){int[] array = new int[]{5,8,6,3,9,2,1,7};bubbleSort(array);System.out.println(Arrays.toString(array));}public static void bubbleSort(int array[]){int tmp = 0;for(int i = 0; i < array.length/2; i++){//有序标记,每一轮的初始值都是trueboolean isSort = true;//奇数轮,从左向右比较和交换for(int j = i; j < array.length - i - 1; j++){if(array[j] > array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;//有元素交换,所以不是有序的,标记变为falseisSort = false;}}if(isSort){break;}//在偶数轮之前,将isSorted重新标记为trueisSort=true;//偶数轮,从右向左比较和交换for(int j=array.length-i-1; j>i; j--){if(array[j] < array[j-1]){tmp = array[j];array[j] = array[j-1];array[j-1] = tmp;//因为有元素进行交换,所以不是有序的,标记变为falseisSort = false;}}if(isSort){break;}}}
代码外层的大循环控制着所有排序回合,大循环内包含2个小循环,第1个小循环从左向右比较并交换元素,第2个小循环从右向左比较并交换元素
优缺点
优点:能够在特定条件下,减少排序的回合数
缺点:代码量几乎增加了1倍
适用场景
大部分元素已经有序的情况
快速排序
介绍
快速排序也属于交换排序,通过元素之间的比较和交换位置来达到排序的目的。快速排序则在每一轮挑选一个基准元素,并让其他比它大的元素移动到数列一边,比它小的元素移动到数列的另一边,从而把数列拆解成两个部分;
这种思路叫做分治法;
流程
在分治法的思想下,原数列在每一轮都被拆分成两部分,每一部分在下一轮又分别被拆分成两部分,直到不可再分为止
每一轮的比较和交换,需要把数组全部元素都遍历一遍,时间复杂度是O(n)。
基准元素选择
基准元素:在分治过程中,以基准元素为中心把其他元素移到它的左右两边。
1.直接选择数列的第1个元素
2.随机选择一个元素
可以随机选择一个元素作为基准元素,并且让基准元素和数列首元素交换位置
元素交换
选定了基准元素以后,我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边,大于基准元素的都交换到基准元素另一边。
有两种实现元素交换的方法:双边循环法、单边循环法
1.双边循环法
实现了元素的交换,让数列中的元素依据自身大小,分别交换到基准元素的左右两边。
使用流程
1.选定基准元素pivot,并且设置两个指针left和right,指向数列的最左和最右两个元素
2.从right指针开始,让指针所指向的元素和基准元素做比较。如果大于或等于pivot,则指针向左移动;如果小于pivot,则right指针停止移动,切换到left指针
3.轮到left指针行动,让指针所指向的元素和基准元素做比较。如果小于或等于pivot,则指针向右移动;如果大于pivot,则left指针停止移动
4.指针大于基准元素时,所指定的元素进行交换,并切换指针
5.当左、右指针重合时,把重合点的元素和基准元素进行交换
代码实现
public static void main(String[] args){int[] array = new int[]{5,8,6,3,9,2,1,7};bubbleSort(array, 0, array.length-1);System.out.println(Arrays.toString(array));}public static void bubbleSort(int[] arr, int startIndex,int endInde){//递归结束:startIndex >= endInde时if(startIndex >= endInde){return;}//得到基准元素int pivotIndex = partition(arr, startIndex, endInde);//根据基准元素,分成两部分进行递归排序bubbleSort(arr,startIndex,pivotIndex-1);bubbleSort(arr,pivotIndex+1,endInde);}/*** 双边循环法,返回基准元素位置* @param arr 待交换的数组* @param startIndex 起始下标* @param endIndex 结束下标* @return*/private static int partition(int[] arr, int startIndex,int endIndex){//取第1个位置(也可以选择随机位置)的元素作为基准元素int pivot = arr[startIndex];int left = startIndex;int right = endIndex;while (left != right){//控制right 指针比较并左移while(left<right && arr[right] > pivot){right--;}//控制left 指针比较并右移while(left<right && arr[left] > pivot){left++;}if(left < right){int p = arr[left];arr[left] = arr[right];arr[right] = p;}}//pivot 和指针重合点交换arr[startIndex] = arr[left];arr[left] = pivot;return left;}
2.单边循环法
双边循环法从数组的两边交替遍历元素,虽然更加直观,但是代码实现相对烦琐。而单边循环法则简单得多,只从数组的一边对元素进行遍历和交换。
使用流程
1.首先选定基准元素pivot。同时,设置一个mark指针指向数列起始位置,这个mark指针代表小于基准元素的区域边界
2.从基准元素的下一个位置开始遍历数组;如果遍历到的元素大于基准元素,就继续往后遍历;如果遍历到的元素小于基准元素,则需要做两件事:第一,把mark指针右移1位,因为小于pivot的区域边界增大了1;第二,让最新遍历到的元素和mark指针所在位置的元素交换位置,因为最新遍历的元素归属于小于pivot的区域
代码实现
public static void main(String[] args){int[] array = new int[]{5,8,6,3,9,2,1,7};bubbleSort(array, 0, array.length-1);System.out.println(Arrays.toString(array));}public static void bubbleSort(int[] arr, int startIndex,int endInde){//递归结束:startIndex >= endInde时if(startIndex >= endInde){return;}//得到基准元素int pivotIndex = partition(arr, startIndex, endInde);//根据基准元素,分成两部分进行递归排序bubbleSort(arr,startIndex,pivotIndex-1);bubbleSort(arr,pivotIndex+1,endInde);}/*** 双边循环法,返回基准元素位置* @param arr 待交换的数组* @param startIndex 起始下标* @param endIndex 结束下标* @return*/private static int partition(int[] arr, int startIndex,int endIndex){//取第1个位置(也可以选择随机位置)的元素作为基准元素int pivot = startIndex;int mark = endIndex;for(int i=startIndex+1; i<=endIndex; i++){if(arr[i]<pivot){mark++;int p = arr[mark];arr[mark] = arr[i];arr[i] = p;}}//pivot 和指针重合点交换arr[startIndex] = arr[mark];arr[mark] = pivot;return mark;}
3.非递归实现
把原本的递归实现转化成一个栈的实现,在栈中存储每一次方法调用的参数
public static void main(String[] args){int[] array = new int[]{5,8,6,3,9,2,1,7};bubbleSort(array, 0, array.length-1);System.out.println(Arrays.toString(array));}public static void bubbleSort(int[] arr, int startIndex,int endInde){Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();Map rootParam = new HashMap();rootParam.put("startIndex", startIndex);rootParam.put("endIndex", endInde);quickSortStack.push(rootParam);while (!quickSortStack.isEmpty()) {Map<String, Integer> param = quickSortStack.pop();int pivotIndex = partition(arr, param.get("startIndex"),param.get("endIndex"));if(param.get("startIndex") < pivotIndex -1){Map<String, Integer> leftParam = new HashMap<String,Integer>();leftParam.put("startIndex", param.get("startIndex"));leftParam.put("endIndex", pivotIndex-1);quickSortStack.push(leftParam);}if(pivotIndex + 1 < param.get("endIndex")){Map<String, Integer> rightParam = new HashMap<String,Integer>();rightParam.put("startIndex", pivotIndex + 1);rightParam.put("endIndex", param.get("endIndex"));quickSortStack.push(rightParam);}}}/*** 双边循环法,返回基准元素位置* @param arr 待交换的数组* @param startIndex 起始下标* @param endIndex 结束下标* @return*/private static int partition(int[] arr, int startIndex,int endIndex){//取第1个位置(也可以选择随机位置)的元素作为基准元素int pivot = startIndex;int mark = endIndex;for(int i=startIndex+1; i<=endIndex; i++){if(arr[i]<pivot){mark++;int p = arr[mark];arr[mark] = arr[i];arr[i] = p;}}//pivot 和指针重合点交换arr[startIndex] = arr[mark];arr[mark] = pivot;return mark;}
非递归方式代码的变动只发生在quickSort方法中。该方法引入了一个存储Map类型元素的栈,用于存储每一次交换时的起始下标和结束下标。
每一次循环,都会让栈顶元素出栈,通过partition方法进行分治,并且按照基准元素的位置分成左右两部分,左右两部分再分别入栈。当栈为空时,说明排序已经完毕,退出循环
相关文章:
数据结构与算法:排序算法(1)
目录 冒泡排序 思想 代码实现 优化 鸡尾酒排序 优缺点 适用场景 快速排序 介绍 流程 基准元素选择 元素交换 1.双边循环法 使用流程 代码实现 2.单边循环法 使用流程 代码实现 3.非递归实现 排序在生活中无处不在,看似简单,背后却隐藏…...
NotePad++ 在行前/行后添加特殊字符内容方法
我们在处理数据时,会遇到需要在每行数据前面、后面、开头、结尾添加各种不一样的字符 如果数据不多,我们可以自己手动的去添加,但如果达到了成百上千行,此时再机械的手动添加是不现实的 这里教给大家如何快速的在数据每行的前后…...
【JavaEE】多线程案例-线程池
文章目录 1. 什么是线程池2. 为什么要使用线程池(线程池有什么优点)3. 如何使用Java标准库提供的线程池3.1 创建一个线程池对象3.2 什么是工厂模式3.3 为什么要使用工厂模式3.4 Executors 创建不同具有不同特性的线程池3.5 ThreadPool 类的构造方法3.6 线…...
服务器搭建(TCP套接字)-fork版(服务端)
基础版的服务端虽然基本实现了服务器的基本功能,但是如果客户端的并发量比较大的话,服务端的压力和性能就会大打折扣,为了提升服务端的并发性能,可以通过fork子进程的方式,为每一个连接成功的客户端fork一个子进程,这样…...
缺失的第一个正数:高效解法与技术
缺失的第一个正数:高效解法与技术 背景 在计算机编程中,有时候需要寻找一个未排序整数数组中没有出现的最小的正整数。这篇技术博客将详细讨论这个问题,并提供一个时间复杂度为 O(n) 且只使用常数级别额外空间的解决方案。 问题描述 leet…...
常用的辅助网站(持续更新)
标题 一、uni-app方向二、H5方向 一、uni-app方向 1、uni-app官网 地址:https://uniapp.dcloud.net.cn/ 2、香蕉云编 地址:https://www.yunedit.com/ 描述:一般用来配置ios证书或安卓证书、上传ios包至商店 3、uView 地址:http…...
LeetCode 75 - 01 : 最小面积矩形
type pair struct{x, y int }func minAreaRect(points [][]int)int{mp : map[pair]struct{}{}// 将二维数组中的坐标映射到map中for i : range points{mp[pair{points[i][0], points[i][1]}] struct{}{}}// 将结果设置为一个最大值,防止影响求最小值的逻辑res : ma…...
每日一题:请解释什么是闭包(Closure)?并举一个实际的例子来说明。(前端初级)
今天继续在前端初级笔试题中被AI虐: 碱面的答案,问题:初级,回答:初级https://bs.rongapi.cn/1702510598371151872/14我的回答如下: 闭包是指由大括号包裹的一个区域,这个区域代表了一个变量生效…...
广告主必看!NetMarvel五大优势驱动出海App投放增长
App出海走到今天,流量红利早就不存在,摆在广告主面前最棘手的两个问题,一是不起量,二是买量成本太高,得不偿失。 如何在确保出海应用用户规模有所增长的同时,也保证整体ROI处在较高水平?NetMar…...
数据结构与算法之复杂度
时间复杂度 1.抓大头 2.常数用o(1),低阶函数也用o(1)代替(直接去掉) 3.取最坏情况 对数相关写法的规定...
ATECLOUD电源测试软件平台如何测试电源纹波?
电源纹波是影响电源稳定性的重要因素,过大的纹波会导致电源模块的工作效率降低,可能使电源模块直接损坏。使用ATECLOUD碘盐测试软件平台对纹波进行测试,检测其工作情况,以确保其稳定性和性能。 电源纹波的产生 电源的纹波通俗的来…...
数据结构与算法:排序算法(2)
目录 堆排序 使用步骤 代码实现 计数排序 适用范围 过程 代码实现 排序优化 桶排序 工作原理 代码实现 堆排序 二叉堆的特性: 1. 最大堆的堆顶是整个堆中的最大元素 2. 最小堆的堆顶是整个堆中的最小元素 以最大堆为例,如果删除一个最大堆的…...
1_图神经网络GNN基础知识学习
文章目录 安装PyTorch Geometric安装工具包 在KarateClub数据集上使用图卷积网络 (GCN) 进行节点分类两个画图函数Graph Neural Networks数据集:Zacharys karate club network.PyTorch Geometric数据集介绍 edge_index使用networkx可视化展示 Graph Neural Networks…...
瑞芯微:基于RK3568的ocr识别
光学字符识别(Optical Character Recognition, OCR)是指对文本资料的图像文件进行分析识别处理,获取文字及版面信息的过程。亦即将图像中的文字进行识别,并以文本的形式返回。OCR的应用场景 卡片证件识别类:大陆、港澳…...
C++真的是 C加加
📝个人主页:夏目浅石. 📌博客专栏:C的故事 🏠学习社区:夏目友人帐. 文章目录 前言Ⅰ. 函数重载0x00 重载规则0x01 函数重载的原理名字修饰 Ⅱ. 引用0x00 引用的概念0x01 引用和指针区分0x03 引用的本质0x04…...
java学习--day5 (java中的方法、break/continue关键字)
文章目录 day4作业今天的内容1.方法【重点】1.1为什么要有方法1.2其实已经见过方法1.3定义方法的语法格式1.3.1无参无返回值的方法1.3.2有参无返回值的方法1.3.3无参有返回值的方法1.3.4有参有返回值的方法 2.break和continue关键字2.1break;2.2continue; 3.案例关于方法的练习…...
MFC主框架和视类PreCreateWindow()函数学习
在VC生成的单文档应用程序中,主框架类和视类均具有PreCreateWindow函数; 从名字可知,可在此函数中添加一些代码,来控制窗口显示后的效果; 并且它有注释说明, Modify the Window class or styles here by…...
for forin forof forEach map区别
一、总结 相同点:都是串行遍历。不同点: 二、for of循环 设计目的:遍历所有数据结构的统一方法。原理:会调用数据结构的Symbol.iterator方法。 只要数据结构定义了Symbol.iterator属性,就能用for of遍历它的成员。…...
特殊时间(蓝桥杯)
特殊时间 问题描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 2022年2月22日22:20 是一个很有意义的时间, 年份为 2022 , 由 3 个 2 和 1 个 0 组成, 如果将月和日写成 4 位, 为 0222 , 也是由 3 个 2 和 1 个 0 组 成…...
VUE路由与nodeJS环境搭建
VUE路由 Vue路由是Vue.js提供的路由管理工具,它允许我们在应用程序中实现页面之间的导航,从而使单页面应用程序的开发更加方便。通过Vue路由,我们可以轻松地创建和管理多个视图,并在这些视图之间导航。 Vue路由使用HTML5的Histo…...
抗锯齿的线
抗锯齿的线 右下角的时候h是0,到顶部 h是1,然后中间y相距4个像素,那dy就是0.25 如果让h abs(fract(h - 0.5) - 0.5) 中间一行0.5,第一行 第三行都是0.25,两端都是0 根据插值来看 这里是 如果用h/dy 那么第一行以上࿰…...
如何使用高压放大器驱动高容性负载
使用高压放大器驱动高容性负载是一个具有挑战性的任务,需要仔细考虑电路设计和操作技巧。下面西安安泰Aigtek将为您介绍一些关于如何使用高压放大器驱动高容性负载的方法和注意事项。 首先,让我们了解一下高容性负载。高容性负载通常指电容值较大的负载元…...
kubernetes集群证书过期启动失败问题解决方法
1、问题现象 执行kubectl命令异常报告 [rootk8s-master1 ~]# kubectl get node The connection to the server 192.168.227.131:6443 was refused - did you specify the right host or port? [rootk8s-master1 ~]# 查看etcd的日志,报错信息如下 {"level&…...
nvm使用的注意事项和常用命令。
nvm官网下载地址:nvm文档手册 - nvm是一个nodejs版本管理工具 - nvm中文网 (uihtm.com) 参考网址:(14 封私信 / 80 条消息) 如何通过 nvm 安装多版本 nodejs?npm 安装失败了怎么办? - 知乎 (zhihu.com) nvm目录下,修…...
代码大全阅读随笔(七)
循环控制 循环控制会出现什么样的错误,任何一种答案都可以归结到下面所说的问题之一:忽略或者错误的对循环执行初始化,忽略了对累加变量或者其他与循环有关变量执行初始化,不正确的嵌套,不正确的循环终止,忽…...
用户与权限管理
文章目录 用户与权限管理1. 用户管理1.1 MYSQL用户1.2 登录MySQL服务器1.3 创建用户1.4 修改用户1.5 删除用户1.6 修改密码1. 修改当前用户密码2. 修改其他用户密码 1.7 MYSQL8密码管理 2. 权限管理2.1 权限列表2.2 授予权限的原则2.3 授予权限2.4 查看权限2.5 收回权限 3. 权限…...
mysql集群使用nginx配置负载均衡
参考链接:https://mu-sl.com//archives/mysql%E9%9B%86%E7%BE%A4%E4%BD%BF%E7%94%A8nginx%E9%85%8D%E7%BD%AE%E8%B4%9F%E8%BD%BD%E5%9D%87%E8%A1%A1 配置文件nginx_tcp.conf 示例 load_module modules/ngx_stream_module.so;stream{upstream tcpssh{hash $remote_…...
蓝桥杯每日一题2023.9.21
蓝桥杯2021年第十二届省赛真题-异或数列 - C语言网 (dotcpp.com) 题目描述 Alice 和 Bob 正在玩一个异或数列的游戏。初始时,Alice 和 Bob 分别有一个整数 a 和 b,有一个给定的长度为 n 的公共数列 X1, X2, , Xn。 Alice 和 Bob 轮流操作࿰…...
知识联合——函数指针数组
前言:小伙伴们又见面啦,今天我们来讲解一个将函数,指针,数组这三个C语言大将整合在一起的知识——函数指针数组。同时来告诉小伙伴们我们上一篇文章的伏笔——函数指针的具体用法。 目录 一.什么是函数指针数组 二.函数指针数组…...
【Nginx26】Nginx学习:日志与镜像流量复制
Nginx学习:日志与镜像流量复制 总算到了日志模块,其实这个模块的指令之前我们就用过了,而且也是是非常常见的指令。相信这一块的学习大家应该不会有什么难度。另一个则是镜像功能,这个估计用过的同学就比较少了,不过也…...
平台网站开发价格/凯里seo排名优化
摘要:基于深度学习的车型识别系统用于识别不同类型的车辆,应用YOLO V5算法根据不同尺寸大小区分和检测车辆,并统计各类型数量以辅助智能交通管理。本文详细介绍车型识别系统,在介绍算法原理的同时,给出Python的实现代码…...
网站开发域名/站长工具ip地址查询
这个例子显示了如何使用QPainter渲染一个简单的QWindow。 值得学习的内容 <QtGui>头文件 #include <QtGui>就可以使用Qt GUI模块中的所有类,当然,愿意的话也可以分开各个include。 QBackingStore与绘制 用于管理基于QPainter的图形的窗口后缓…...
变身 变装 wordpress/什么是seo标题优化
当我发送JSON对象数组我的jQuery的AJAX方法能够解析内容和显示数据在ListView的jQuery,但是当我只有一个单一的对象我相同的jquery ajax方法不能解析数据。JQuery的Ajax方法工作与多个JSON对象,但不与单个JSON对象这里我的JSON对象数组:{&quo…...
外贸wordpress主题/app推广平台排行榜
燕山大学计算机组成原理硕士研究生入学考试大纲 燕山大学计算机组成原理硕士研究生入学考试大纲 考研加油站收集整理 http://doc.xuehai.net《计算机组成原理 》考研复习教学大纲【指定教学参考书】:计算机组成原理;哈尔滨工业大学:唐朔飞编著…...
中国互联网协会网站/能让手机流畅到爆的软件
在实际工作中经常遇到以下问题:邮件发送给错误的收件人,简而言之就是邮件发错了,如果遇到群发更麻烦。Exchange中提供了批量删除邮件功能,当用户发现发送错误后,管理员可以检索并删除指定的邮件。 案例任务:…...
做网站 做app/港港网app下载最新版
webpack 打包生成文件的时候,为了防止缓存,会在文件后边跟上版本号或者hash值,采用版本号的时候,一些小的修改,必须更改版本号,不然就会造成缓存。这样并不符合我的业务需求,所以我们将文件后边…...