算法第4版 第2章排序

综述:5个小节,四种排序+应用,初级排序、归并排序、快速排序、优先队列

===2.1.初级排序===

排序算法模板,less(), exch(), 排序代码在sort()方法中;

选择排序:如升序排列,1.找到数组中最小的元素;2.与数组中的第一个元素交换下位置;3.再在剩下的元素找最小值,与第二个元素交换下位置;重复,直到所有元素都完成排序。

交换的总次数是n,算法的时间效率取决于比较次数(N2/2);

选择排序时间复杂度(O(n2)),两个特点:运行时间与输入无关;数据移动是最少的;

选择排序的实现:

private static boolean less(Comparable v, Comparable w){

return v.compareTo(w)<0;

}

public static void exch(Comparable[]a, int i, int j){

Comparable t = a[i]; a[i]=a[j];a[j]=t;

}

public class Selection{

public static void sort(Comparable[]){

int N = a.length;

for(int i = 0; i<N;i++){

int min =i;

for(int j =i+1;j<N;j++){

if(less a[j], a[min]) min =j;

exch(a, i, min);

}

}

}

冒泡排序:一次比较两个元素,如果位置不对就交换,一次遍历要交换多次

插入排序:第i个元素与第i之前的元素对比,插入到合适的位置。左侧部门一直为有序数组

对于随机排列的长度未N且主键不重复的数组,平均情况下插入排序需要N2/4比较,N2/4次交换。最坏情况下需亚奥N2/2, N2/2次交换。插入排序对有序数组的排序,运行时间是线性的。

代码实现:

publIc class Insertion{

public static void sort(Comparable[] a){

int N = a.length;

for(int i = 1; i<N; i++){

for(int j =1; j>0&&less(a[j], a[j-1]); j--)

exch(a, j, j-1);

}

}

}

部分有序数组:数组中的每个元素距离它的最终位置都不远;一个有序的大数组接一个小数组;数组中只有几个元素的位置不正确。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说,一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组(见图2.1.2)。在进行排序时,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便。用这种方式,对于任意以1结尾的h序列,我们都能够将数组排序。这就是希尔排序。

代码实现:

public class Shell{

public static void sort(Comparable[] a){

int N = a.length;

int h =1;

while(h<N/3) h = 3*h+1;

while(h>=1){

for(int i =h; i<N; i++){

for(int j=i, j>=h&&less(a[j],a[j-h]); j -=h)

exch(a, j, j-h);

}

h = h/3;

}

}

}

===2.2 归并排序===

归并,将两个有序数组归并成一个更大的有序数组。

归并排序,能够保证任意长度为N的数组排序所需时间和NlogN成正比,缺点是所需的额外空间与N成正比。

实现归并直接的方法,将两个不同的有序数组归并到第三个数组中,创建一个适当大小的数组,然后将两个输入数组的元素一个个从小到大放入这个数组中。

归并一个大数组时,需进行多次归并,每次归并都要创建一个新数组存储排序结果。通过原地归并,先将前半部分排序,再将后半部分排序,在数组中移动元素而不需要使用额外的空间。

merge(a, lo, mid, hi)它会将子数组a[lo...mid]和a[mid+1..hi]归并成一个有序数组,并将结果存放在a[lo..hi],

原地归并的抽象方法:

public static void merge(Comparable[] a, int lo, int mid, int hi){

int i = lo, j+mid+1;

for(int k =lo; k <= hi; k++) aux[k] = a[k];

for(int k =lo; k<=hi; k++)

if(i>mid) a[k]=aux[j++];

else if(j >hi) a[k]=aux[i++];

else if(less(aux[j], aux[i])) a[k] =aux[j++];

else a[k]=aux[i++];

}

该方法先将所有元素复制到aux[], 然后再归并回a[],方法再归并时进行了4个条件判断,左半边用尽(取右半边元素),右半边用尽(取左半边元素),右半边的当前元素小于左半边的当前元素(取右半边的元素),以及右半边的当前元素大于等于左半边的当前元素(取左半边的元素)

自顶向下的归并排序

public class Merge{

private static Comparable[] aux;

public static void sor(Comparable[] a){

aux = new Comparable[a.length];

sort(a, a.length-1);

}

private static void sort(Comparable[] a, int lo, int hi){

if(hi<=lo) return;

int mid = lo+(hi-lo)/2;

sort(a, lo, mid);

sort(a, mid+1, hi);

merge(a, lo, mid, hi);

}

}

自底向上的归并排序

public class MergeBu{

private static Comparable[] aux;

public static void sort(Comparable[] a){

int N =a.length;

aux = new Comparable[N];

for(int sz =1; sz<N; sz =sz+sz){

for(int lo=0; lo<N-sz; lo+=sz+sz)

merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));

}

}

}

===2.3快速排序===

快速排序时间复杂度(O(nlogn));

特点:原地排序(只需要一个很小的辅助栈),且将长度为N的数组排序所需的时间和NlgN成正比。

快速排序:分治的排序算法,将一个数组分成两个子数组,独立的排序。与归并排序互补,

并排序将数组分成两个子数组分别排序,并将有序的子数组归并以将整个数组排序;而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中,递归调用发生在处理整个数组之前;在第二种情况中,递归调用发生在处理整个数组之后。

在归并排序中,一个数组被等分为两半;在快速排序中,切分(partition)的位置取决于数组的内容

public class Quick

{ public static void sort(Comparable[] a) {

StdRandom.shuffle(a)

; // 消除对输入的依赖 sort(a, 0, a.length -1); }

private static void sort(Comparable[] a, int lo, int hi)

{ if (hi <= lo) return; int j = partition(a, lo, hi); // 切分(请见“快速排序的切分”)

sort(a, lo, j-1); // 将左半部分a[lo .. j-1]排序

sort(a, j+1, hi); // 将右半部分a[j+1 .. hi]排序

} }

该方法的关键在于切分,这个过程使得数组满足下面三个条件:❏对于某个j, a[j]已经排定;❏ a[lo]到a[j-1]中的所有元素都不大于a[j];❏ a[j+1]到a[hi]中的所有元素都不小于a[j]。通过递归地调用切分来排序的。

因为切分过程总是能排定一个元素,用归纳法不难证明递归能够正确地将数组排序:如果左子数组和右子数组都是有序的,那么由左子数组(有序且没有任何元素大于切分元素)、切分元素和右子数组(有序且没有任何元素小于切分元素)组成的结果数组也一定是有序的。

需要实现切分方法。一般策略是先随意地取a[lo]作为切分元素,即那个将会被排定的元素,然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素,再从数组的右端开始向左扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的,因此我们交换它们的位置。

当两个指针相遇时,我们只需要将切分元素a[lo]和左子数组最右侧的元素(a[j])交换然后返回j即可

快速排序的最好情况是每次都正好能将数组对半分。在这种情况下快速排序所用的比较次数正好满足分治递归的CN=2CN/2+N公式。2CN/2表示将两个子数组排序的成本,N表示用切分元素和所有数组元素进行比较的成本

几个细节问题:原地切分、别越界、保持随机性、终止循环、处理切分元素值有重复的情况、终止递归

算法改进:

切换到插入排序(对于小数组,快速排序比插入排序慢;因为递归,快速排序的sort()方法在小数组中也会调用自己);

改进快速排序性能的第二个办法是使用子数组的一小部分元素的中位数来切分数组。这样做得到的切分更好,但代价是需要计算中位数。人们发现将取样大小设为3并用大小居中的元素切分的效果最好;

熵最优的排序,含有大量重复元素的数组,一个元素全部重复的子数组就不需要继续排序了,但我们的算法还会继续将它切分为更小的数组,一个简单的想法是将数组切分为三部分,分别对应小于、等于和大于切分元素的数组元素。这种切分实现起来比我们目前使用的二分法更复杂

==2.4优先队列===

许多应用程序都需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。很多情况下我们会收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键值最大的元素

例如,你可能有一台能够同时运行多个应用程序的电脑(或者手机)。这是通过为每个应用程序的事件分配一个优先级,并总是处理下一个优先级最高的事件来实现的。例如,绝大多数手机分配给来电的优先级都会比游戏程序的高。

在这种情况下,一个合适的数据结构应该支持两种操作:删除最大元素和插入元素。这种数据类型叫做优先队列。优先队列的使用和队列(删除最老的元素)以及栈(删除最新的元素)类似。

基于二叉堆数据结构的一种优先队列的经典实现方法,用数组保存元素并按照一定条件排序,以实现高效地(对数级别的)删除最大元素和插入元素操作。

优先队列的一些重要的应用场景包括模拟系统,其中事件的键即为发生的时间,而系统需要按照时间顺序处理所有事件;任务调度,其中键值对应的优先级决定了应该首先执行哪些任务;

泛型优先队列的API,优先队列是一种抽象数据类型(请见1.2节),它表示了一组值和对这些值的操作。优先队列最重要的操作就是删除最大元素和插入元素,删除最大元素的方法名为delMax(),插入元素的方法名为insert()

优先队列的调用示例:考虑以下问题:输入N个字符串,每个字符串都对应着一个整数,你的任务就是从中找出最大的(或是最小的)M个整数(及其关联的字符串)。要我们能够高效地实现insert()和delMin(),下面的优先队列用例中调用了MinPQ的TopM就能使用优先队列解决这个问题。

初级实现:数组实现(无序)、数组实现(有序)、链表表示法

堆的定义:数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中,每个元素都要保证大于等于另两个特定位置的元素。相应地,这些位置的元素又至少要大于等于数组中的另两个元素。

当一棵二叉树的每个结点都大于等于它的两个子结点时,它被称为堆有序。

如果我们用指针来表示堆有序的二叉树,那么每个元素都需要三个指针来找到它的上下结点(父结点和两个子结点各需要一个)。

由下至上的堆有序化(上浮)、由上至下的堆有序化(下沉)、多叉堆、调整数组大小、元素的不可变性、索引优先队列、索引优先队列用例。

用基于堆的优先队列这样做等同于哪种排序?一种全新的排序方法!下面我们就用堆来实现一种经典而优雅的排序算法——堆排序。

堆排序可以分为两个阶段。在堆的构造阶段中,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按递减顺序取出所有元素并得到排序结果。

从右至左用sink()函数构造子堆。数组的每个位置都已经是一个子堆的根结点了,sink()对于这些子堆也适用。如果一个结点的两个子结点都已经是堆了,那么在该结点上调用sink()可以将它们变成一个堆。这个过程会递归地建立起堆的秩序。开始时我们只需要扫描数组中的一半元素,因为我们可以跳过大小为1的子堆。最后我们在位置1上调用sink()方法,扫描结束。

堆的构造、下沉排序、先下沉后上浮。

堆排序在排序复杂性的研究中有着重要的地位,因为它是我们所知的唯一能够同时最优地利用空间和时间的方法——在最坏的情况下它也能保证使用~2NlgN次比较和恒定的额外空间。

2.5 应用

排序如此有用的一个主要原因是,在一个有序的数组中查找一个元素要比在一个无序的数组中查找简单得多。只要队列是有序的,很多其他任务也更容易完成。

排序算法的一种典型应用就是商业数据处理。

我们在类的定义中实现一个恰当的compareTo()方法就可以做到这一点。这样我们在处理Transaction类型的数组a[]时就可以先将其排序,比如这样Quick.sort(a)。我们的排序算法对Transaction类型一无所知,但Java的Comparable接口使我们可以为该类型定义大小关系,这样我们的任意排序算法都能够用于Transaction对象了。

Java系统库的排序算法,这里我们考虑Java系统库中的主要排序方法java.util. Arrays.sort()。

ava的系统程序员选择对原始数据类型使用(三向切分的)快速排序,对引用类型使用归并排序。这些选择实际上也暗示着用速度和空间(对于原始数据类型)来换取稳定性(对于引用类型)。

排序应用一览:商业计算、信息搜索(有序的信息确保我们可以用经典的二分查找法(见第1章)来进行高效的搜索)、运筹学、事件驱动模拟、数值计算、组合搜索

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

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

相关文章

一种DevOpts的实现方式:基于gitlab的CICD(一)

写在之前 笔者最近准备开始入坑CNCF毕业的开源项目&#xff0c;看到其中有一组开源项目的分类就是DevOpts。这个领域内比较出名的项目是Argocd&#xff0c;Argo CD 是一个用于 Kubernetes 的持续交付 (Continuous Delivery) 工具&#xff0c;它以声明式的方式实现了应用程序的…

【Docker】配置阿里云镜像加速器

默认情况下&#xff0c;将来从docker hub &#xff08;https://hub.docker.com )上下载镜像太慢&#xff0c;所以一般配置镜像加速器。 没有账号的注册一个账号并登录 登录之后点击控制台 查看 cat /etc/docker/daemon.json

【大数据进阶第三阶段之Hive学习笔记】Hive安装

目录 1、环境准备 2、下载安装 3、配置环境变量 4、配置文件 4.1、配置hive-env.sh ​编辑4.2、配置hive-site.xml 5、上传配置jar 6、启动 1、环境准备 安装hadoop 以及 zookeeper、mysql 【大数据进阶第二阶段之Hadoop学习笔记】Hadoop 运行环境搭建-CSDN博客 《z…

C++上位软件通过Snap7开源库访问西门子S7-200/LOGO PLC/合信M226ES PLC V存储区的方法

前言 在前面例程中谈到了C 通过Snap7开源库S7通信库跟西门子S7-1200PLC/S7-1500PLC以及合信CTMC M226ES PLC/CPU226 PLC通信的方式方法和应用例程。但是遗憾的是Snap7中根据官方资料显示只能访问PLC的 DB区、MB区、C区、T区 、I区、Q区&#xff0c;并没有提到有关如何访问S7-20…

HNU-数据库系统-作业

数据库系统-作业 计科210X 甘晴void 202108010XXX 第一章作业 10.09 1.(名词解释)试述数据、数据库、数据库管理系统、数据库系统的概念。 数据&#xff0c;是描述事物的符号记录。 数据库&#xff08;DB&#xff09;&#xff0c;是长期存储在计算机内、有组织、可共享的大量…

蓝桥杯练习题(二)

&#x1f4d1;前言 本文主要是【算法】——蓝桥杯练习题&#xff08;二&#xff09;的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 …

音乐制作软件Studio One mac有哪些特点

Studio One mac是一款专业的音乐制作软件&#xff0c;该软件提供了全面的音频编辑和混音功能&#xff0c;包括录制、编曲、合成、采样等多种工具&#xff0c;可用于制作各种类型的音乐&#xff0c;如流行音乐、电子音乐、摇滚乐等。 Studio One mac软件特点 1. 直观易用的界面&…

软件测试|详解 Pytest 参数化:简化测试用例的编写

简介 Pytest 是一个广泛使用的 Python 测试框架&#xff0c;它提供了丰富的功能来编写和执行测试用例。其中一个强大的特性是参数化&#xff0c;它允许我们通过一种简洁的方式运行多个输入参数的相似测试用例&#xff0c;从而减少冗余的代码。本文将详细介绍 Pytest 的参数化功…

如何给字符串字段添加索引

MySQL是支持前缀索引的&#xff0c;可以定义字符串的一部分作为索引&#xff0c;如果创建索引的语句不指定前缀长度&#xff0c;那么索引就会包含整个字符串。 alter table SUser add index index1(email);alter table SUser add index index2(email(6)); 如上两个创建索引的语…

嵌入式培训机构四个月实训课程笔记(完整版)-Linux系统编程第十天-Linux下mplayer音乐播放器练习题(物联技术666)

更多配套资料CSDN地址:点赞+关注,功德无量。更多配套资料,欢迎私信。 物联技术666_嵌入式C语言开发,嵌入式硬件,嵌入式培训笔记-CSDN博客物联技术666擅长嵌入式C语言开发,嵌入式硬件,嵌入式培训笔记,等方面的知识,物联技术666关注机器学习,arm开发,物联网,嵌入式硬件,单片机…

Mondo备份linux操作系统为iso镜像 —— 筑梦之路

简介 Mondo Rescue&#xff08;以下简称Mondo&#xff09;可以说是Linux 下的Ghost&#xff0c;它可以将你的系统像照相一样备份至磁带&#xff0c;CD-R&#xff0c;CD-RW&#xff0c;NFS或硬盘分区。Mondo广泛支援LVM&#xff0c;RAID&#xff0c;ext2, ext3, JFS, XFS,Reise…

第十二届全国大学生GIS技能大赛试题、数据以及解题思路

一、赛题说明 第十二届全国大学生GIS应用技能大赛试题&#xff0c;共分为上午和下午两部分 上午题 上午的题和往届的没啥区别&#xff0c;还是偏向于考数据整合、空间配准、数字化等基础的数据处理能力。 下午两套题都需要做哟 第一套 第二套&#xff0c;考察三维分析 关于…

知识引导的分子生成扩散模型 - KGDiff 评测

一、背景介绍 KGDiff模型是一个基于口袋的知识引导的3D分子生成的扩散模型&#xff0c;来源于上海交通大学计算机学院涂仕奎教授的文章&#xff1a; 《KGDiff: towards explainable target-aware molecule generation with knowledge guidance》。文章链接&#xff1a;*KGDiff…

LeetCode 145. 二叉树的后序遍历

145. 二叉树的后序遍历 给你一棵二叉树的根节点 root &#xff0c;返回其节点值的 后序遍历 。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[3,2,1]示例 2&#xff1a; 输入&#xff1a;root [] 输出&#xff1a;[]示例 3&#xff1a; 输入&…

20240107让Firefly的AIO-3399J开发板的Android11下配置为默认1080p录像

20240107让Firefly的AIO-3399J开发板的Android11下配置为默认1080p录像 2024/1/7 23:01 开发板&#xff1a;Firefly的AIO-3399J【RK3399】 SDK&#xff1a;rk3399-android-11-r20211216.tar.xz【Android11】 Android11.0.tar.bz2.aa【ToyBrick】 Android11.0.tar.bz2.ab Androi…

[论文阅读]4DRadarSLAM: A 4D Imaging Radar SLAM System for Large-scale Environments

目录 1.摘要和引言&#xff1a; 2. 系统框架&#xff1a; 2.1 前端&#xff1a; 2.2 回环检测&#xff1a; 2.3 后端&#xff1a; 3.实验和分析&#xff1a; 4.结论 1.摘要和引言&#xff1a; 这篇论文介绍了一种名为“4DRadarSLAM”的新型4D成像雷达SLAM系统&#xff0…

springboot基于Web的社区医院管理服务系统源码和论文

在Internet高速发展的今天&#xff0c;我们生活的各个领域都涉及到计算机的应用&#xff0c;其中包括社区医院管理服务系统的网络应用&#xff0c;在外国线上管理系统已经是很普遍的方式&#xff0c;不过国内的管理系统可能还处于起步阶段。社区医院管理服务系统具有社区医院信…

服务发现Discovery

对于注册进eureka里面的微服务&#xff0c;可以通过服务发现来获得该服务的信息 1、 修改cloud-provider-payment8001的controller import com.my.springcloud.utils.RestResponse; import com.my.springcloud.entities.Payment; import com.my.springcloud.service.PaymentSe…

java火车查询管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java Web火车查询管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql…

SpringBoot+vue2.0开发在线考试系统网页

目录 一、需求分析 二、技术需求 三、功能分析 四、数据库设计 五、界面展示 六、资源获取 一、需求分析 在线考试系统是一种基于互联网的电子化考试平台&#xff0c;它提供了一系列功能来支持教育机构、企业或组织进行在线考试和评估。 以下是在线考试系统的一些常见功…