快速排序(QuickSort)-归并排序(MergeSort)[java编写]

1. 快速排序

1.1 基本概述

快速排序采用分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot 将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。、

1.2 图解

1.3 快速排序的代码实现(java)

class QuickSort {public static void sort(int[] array) {sortSection(array, 0, array.length - 1);}private static void sortSection(int[] array, int start, int end) {// 递归的baseCaseif(start >= end) {return;}// 递归分块并排序int p = partition(array,start,end);sortSection(array, start, p - 1);sortSection(array, p + 1, end);}/*** partition 方法目的在于将目标数组分以pivot为界,分为两部分,并返回pivot应在的的位置-                            biggest_smallest* @param array    目标数组* @param start    开始位置* @param end      结束位置* @return         返回分割后的pivot位置-biggest_smallest*/private static int partition(int[] array,int start,int end) {int pivot = array[start];int biggest_smallest = start;int tmp;// 以pivot为隔板,小的放左边,大的放右边for(int i = start + 1; i <= end; i++) {if(array[i] < pivot) {biggest_smallest++;tmp = array[biggest_smallest];array[biggest_smallest] = pivot;array[i] = tmp;}}array[start] = array[biggest_smallest];array[biggest_smallest] = pivot;return biggest_smallest;}
}

1.4 快速排序的时间复杂度

快速排序是一种常用的排序算法,它的时间复杂度在不同情况下有所不同。在最佳情况下,快速排序的时间复杂度为O(n log n),而在最差的情况下,其时间复杂度为O(n ^ 2)。平均情况下,快速排序也能达到O(nlogn) 的时间复杂度。

快速排序的性能高度依赖于选择的基准值,如果每次能将数组分为两个大小大致相等的子数组,那么快速排序的效率最高。在这种情况下,排序过程可以看作是一个平衡二叉树,其中每个节点的操作时间为O(n),树的高度为O(logn)。因此,整个排序过程的时间复杂度为O(n logn)。

在最差情况下,如果每次选择的基准值都是最小或最大的元素,那么数组将不会被平均分割,导致递归深度为O(n),每次的操作时间仍未O(n),因此总的时间复杂度为O(n^2)。

尽管快速排序在最差情况下的时间复杂度较高,但由于其在平均情况下的高效性,以及它的就地排序特性(不需要额外的存储空间),快速排序通常优于其他排序算法,如归并排序。此外,快速排序的局部性引用优势使得它在实际应用中的表现通常比理论分析更好。

1.5 快速排序的空间复杂度

快速排序的空间复杂度主要由递归调用栈产生。在最佳情况下,递归树的深度为O(log n),因此空间复杂度也为O(log n),在最差的情况下,递归树退化为线性链,空间复杂度为O(n)。平均情况下,空间复杂度同样为O(log n)。

2. 归并排序

2.1 基本概述

归并排序是一种高效的排序算法,由约翰.冯.诺依曼于1945年发明,它利用了分治法(Divide and Conquer) 的策略来实现排序。归并排序的核心思想是将一个大问题分解成小问题解决,然后将小问题的解决结果合并以解决原来的大问题。

归并排序将待排序的数组分成两部分,对每部分递归地应用归并排序,然后将两个有序的子数组合并成一个有序的数组。这个过程一直重复,直到数组完全有序。归并排序的过程可以用一棵完全二叉树来形象地表示,其中每个节点表示一个排序操作或合并操作。

2.2 图解

先拆分

后合并

2.3 归并排序的代码实现

class MergeSort {public static void sort(int [] array){sortSection(array,0,array.length - 1);}private static void sortSection(int[] array,int start,int end){// 递归的baseCaseif(start == end) {return;}// 通过递归实现了数据按归并排序算法的拆分int mid = (start + end) / 2;sortSection(array,start,mid);sortSection(array,mid + 1,end);// 调用merge方法对数据进行合并merge(array,start,mid + 1,end);}/*merge 方法实现了两块数据的合并阶段*/private static void merge(int[] array,int start,int start2,int end) {int len1 = start2 - start;int[] tmp = new int[len1];System.arraycopy(array,start,tmp,0,len1);int p1 = 0;int p2 = start2;for(int i = start;i <= end;i++) {if(tmp[p1] <= array[p2]) {array[i] = tmp[p1];p1++;if(p1 == len1) {break;}}else {array[i] = array[p2];p2++;if(p2 > end){while(p1 < len1){i++;array[i] = tmp[p1];p1++;}}}}}
}

2.4 归并排序的时间复杂度

归并排序是一种基于分治法的有效排序算法,它将一个数组分为两个子数组,递归地将子数组分到只有一个元素,然后合并这些子数组以使整个数组有序。归并排序的一个关键步骤是合并两个已排序的子数组,这个过程需要遍历所有元素以确保它们正确排序。

归并排序的时间复杂度主要由两个部分组成:数组分割和数组合并。在分割阶段,数组被递归地分成两半,直到每个子数组只有一个元素,这个过程的时间复杂度是O(og n),因为每次风格都将数组的大小减半。在合并阶段,每个元素都需要被比较和移动以合并两个字数组,这个过程的时间复杂度是O(n)。

因此,归并排序的总体时间复杂度是O(n log n),这是因为每个分割步骤都需要一次完整的元素合并。这个时间复杂度使用于最好,最坏和平均情况,因为无论数组的初始顺序如何,分割和合并的步骤都是固定的。

2.5 归并排序的空间复杂度

归并排序的空间复杂度是O(n),这是因为合并过程需要与原始数组相同数量的额外空间来存储合并后的数组。这个额外的空间通常是通过一个临时数组来实现的,临时数组在整个排序过程中用与存储合并的结果。

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

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

相关文章

参会邀请 | 第二届机器视觉、图像处理与影像技术国际会议(MVIPIT 2024)

第二届机器视觉、图像处理与影像技术国际会议&#xff08;MVIPIT 2024&#xff09;将于2024年9月13日-15日在中国张家口召开。 MVIPIT 2024聚焦机器视觉、图像处理与影像技术&#xff0c;旨在为专家、学者和研究人员提供一个国际平台&#xff0c;分享研究成果&#xff0c;讨论…

算法训练营——day3长度最小子数组

1 长度最小子数组-力扣209&#xff08;中等&#xff09; 1.1 题目&#xff1a; 长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返…

基于orangePi的智能家居系统

目录 一.接线图 1.orangePi接线 2.继电器接线 二.语音模块的配置 1.pin脚的配置 2.命令词自定义信息 三.测试 1.通过gpio指令测试烟雾检测器是否正确连接 2.编写脚本测试其他模组接线是否正常 四.人脸识别方案 1.首先开通人脸搜索识别服务 2. 点击产品控制台,向人…

2024年四川省安全员B证证考试题库及四川省安全员B证试题解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年四川省安全员B证证考试题库及四川省安全员B证试题解析是安全生产模拟考试一点通结合&#xff08;安监局&#xff09;特种作业人员操作证考试大纲和&#xff08;质检局&#xff09;特种设备作业人员上岗证考试大…

ARM----时钟

时钟频率可以是由晶振提供的&#xff0c;我们需要高频率&#xff0c;但是外部接高的晶振会不稳定&#xff0c;所有使用PLL&#xff08;锁相环&#xff09;来放大频率。接下来就让我们学习用外部晶振提供的频率来配置时钟频率。 一.时钟源的选择 在这里我们选择外部晶振作为时钟…

数据库面试题学习

B树和B树 B树 排好序的 节点内部有多个元素 B树 排好序的 节点内多个元素 叶子节点有指针&#xff08;双向指针&#xff09; 非叶子节点冗余了一份在叶子节点 mysql定义B树 InnoDB B树是B树的升级版~ InnoDB b树是怎么产生的 mysql 页 目录 16KB 自增id uuid 一页最多可以存储…

【精选】文件摆渡系统:跨网文件传输的安全与效率之选

文件摆渡系统可以解决哪些问题&#xff1f; 文件摆渡系统&#xff08;File Shuttle System&#xff09;主要是应用于不同网络、网段、区域之间的文件数据传输流转场景&#xff0c; 用于解决以下几类问题&#xff1a; 文件传输问题&#xff1a; 大文件传输&#xff1a;系统可…

Windows bat脚本学习九(srec_cat)

一、简介 srec_cat是一个在嵌入式开发中&#xff0c;使用非常频繁的软件&#xff0c;这里做个常用功能的介绍。 二、常用参数 文件类型 在使用srec_cat指令时&#xff0c;在输入文件和输出文件时&#xff0c;要指明文件的类型&#xff0c;如&#xff1a; input.hex -intel …

2024国赛数学建模C题完整论文:农作物的种植策略

农作物种植策略优化的数学建模研究&#xff08;完整论文&#xff0c;持续更新&#xff0c;大家持续关注&#xff0c;更新见文末名片 &#xff09; 摘要 在本文中&#xff0c;建立了基于整数规划、动态规划、马尔科夫决策过程、不确定性建模、多目标优化、相关性分析、蒙特卡洛…

网络层 VII(IP多播、移动IP)【★★★★★★】

一、IP 多播 1. 多播的概念 多播是让源主机一次发送的单个分组可以抵达用一个组地址标识的若干目的主机&#xff0c;即一对多的通信。在互联网上进行的多播&#xff0c;称为 IP 多播&#xff08;multicast , 以前曾译为组播&#xff09;。 与单播相比&#xff0c;在一对多的…

Linux_kernel移植uboot07

一、移植 根据硬件平台的差异&#xff0c;将代码进行少量的修改&#xff0c;修改过后的代码在目标平台上运行起来 移植还需要考虑硬件环境&#xff0c;驱动只需要考虑内核的环境 二、移植内容 1、移植Uboot uboot属于bootloader的一种&#xff0c;还有其他的bootloader&#x…

【超简单】1分钟解决ppt全文字体一键设置

省流 ppt的全部字体需要在“幻灯片母版”里面&#xff0c;“自定义字体”去设置好标题与正文的字体之后才算全部设置完毕 “视图”---“幻灯片母版” 找到“字体”---“自定义字体” 设置好中文和西文的字体&#xff0c;都可以按照自己的选择来&#xff0c;保存即可 吐槽 之…

通信工程学习:什么是FEC前向纠错

FEC&#xff1a;前向纠错 FEC&#xff08;Forward Error Correction&#xff0c;前向纠错&#xff09;是一种增加数据通信可信度的技术&#xff0c;广泛应用于计算机网络、无线通信、卫星通信等多种数据传输场景中。其基本原理和特点可以归纳如下&#xff1a; 一、FEC前向纠错…

固态硬盘装系统有必要分区吗?

前言 现在的新电脑有哪一台是不使用固态硬盘的呢&#xff1f;这个好像很少很少了…… 有个朋友买了一台新的笔记本电脑&#xff0c;开机之后&#xff0c;电脑只有一个分区&#xff08;系统C盘500GB&#xff09;。这时候她想要给笔记本分区…… 这个真的有必要分区吗&#xf…

golang关于slice map函数传参的小问题

问题 函数传参了一个slice&#xff0c;在函数内触发了对长度的修改&#xff08;添加或删除&#xff09;&#xff0c;但是未影响函数外的实参由此产生了另一个问题&#xff0c;我们用map在函数内修改会不会有影响不到实参的情况&#xff1f; 结论 map作为函数参数时是引用传递…

TCP 拥塞控制

概念详解 TCP拥塞控制是网络通信中的一个关键机制&#xff0c;它通过动态调整发送数据的速率来避免网络拥塞。以下是TCP拥塞控制的详细概念解释&#xff1a; 拥塞窗口&#xff08;CWND, Congestion Window&#xff09;: 定义&#xff1a;发送方在收到接收方的确认&#xff08;…

Java 面试题:通过JProfile排查OOM问题 内存溢出与内存泄漏问题 --xunznux

文章目录 如何通过JProfile排查OOM或内存泄漏问题1、启动工具观测程序执行状态2、使用默认设置采样3、查看memory&#xff0c;Run GC无效4、查看 Live Memory发现两个byte大数组存在5、通过快照查看堆中的内存使用情况6、找到Full GC无法清除的对象通过大对象列表定位内存泄漏问…

【SpringBoot】电脑商城-12-订单功能

创建订单 1 订单-创建数据表 1.使用use命令先选中store数据库。 USE store;2.在store数据库中创建t_order和t_order_item数据表。 CREATE TABLE t_order (oid INT AUTO_INCREMENT COMMENT 订单id,uid INT NOT NULL COMMENT 用户id,recv_name VARCHAR(20) NOT NULL COMMENT …

Mac 上 YYDS 的自动切换输入法工具:好用到原地炸裂式起飞

有一种幸福的状态就是 任何时刻你都可以全力以赴 被打断、被终止也没有遗憾 因为你对结果没有那么期待 而且已经用尽全力了 当你深刻认识到你所做的事情 是多么好的时候 自然会产生一种想要分享出去 的心情 如今社会大部分工作都被电脑化了&#xff0c;在很多方面我们的…