排序
第八章 排序基本概念和排序方法排序的基本概念
排序:从大到小或从小到大排序
排序的稳定性:
稳定的:关键字相同的元素在排序之后相对位置不变
不稳定:相反
排序算法的分类:
内部排序:待排序记录全部放在计算机内存中*(关注算法时间、空间复杂度)*
外部排序:数据过大,以至于内存中不能容纳全部的数据,在排序过程中,尚需对外存进行访问排序*(还要关注读取/写磁盘的次数更少)*
插入排序算法思想︰每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。
直接插入排序是一种最简单的排序方法,其基本操作是将一条记录插入已经排好序的表,从而得到一条新的、记录数量增1的有序表
算法描述:
算法分析:
时间复杂度:
最好的情况:比较次数n-1次
最坏的情况:$$O(n^2)$$
平均时间复杂度:$$O(n^2)$$
空间复杂度:$$O(1)$$
折半插入排序
时间复杂度依然是$O(n^2)$
注意:一直到low>high时才停止折半查找。当mid所指元素等于当前元素时,应继续令low=mid+1,以保证“稳定性”。最终应将 ...
线性表
线性表线性表的顺序表示和实现
初始化
步骤:
为顺序表L动态分配一个预定义大小的数组空间,使elem指向这段空间的基地址
将表的当前长度设为0
代码:
1234567891011//初始化const int MAXSIZE = 100;bool InitList(SqList L){ L.elem = new ElemType[MAXSIZE]; if(!L.elem){ return 0; } L.length = 0; return true;}
取值
步骤:
判断指定的位置序号i的值是否合理$$(1<=i<=L.length)$$,若不合理,返回false
若值合理,则将第i个数据元素L.elem[i-1]赋值参数e,通过e返回第i个数据元素的传值
123456789//取值int GetElem(SqList L,int i,ElemType e){ if(i<1 || i>L.length){ ret ...
I/O流
I/O流文件概念1、文件
保存数据的地方
2、 文件流
流:数据在数据源(文件)和程序(内存)之间的路径
输入流:将磁盘中的文件写入内存
输出流:将内存中的内容写入磁盘
文件操作
创建文件对象相关的构造器和方法
new File(String pathname)根据路径创建一个File对象
new File(File parent,String chil)根据父目录文件+子路径构建
new File(String parent,String child)根据父目录+子路径构建
createNewFile创建新文件
获取文件的相关信息
getName、getAbsolutePath、getParent、length、exists、isFile、isDirectory
目录操作和文件删除
创建一级目录:mkdir
创建多级目录:mkdirs
删除空目录或文件:delete
IO流原理及流的分类
Java IO原理
IO流是input、output的缩写,用于处理数据传输,如读写文件、网络通信
在Java程序中,对于数据的输入。输出以“流(stream)”的方式 ...
Java设计思想
思想统计
统计思想:利用map集合进行统计
遍历
遍历集合,按照指定的集合进行拼接的两种方式:
StringBuilder
StringJoiner
概率问题
如30%的甲,70%的乙:
创建一个新的集合:赋30%的”1”,赋70%的”2”
对所创建的集合元素进行随机取值:Random r = new Random();
对随机取得的值进行条件判断,取到的值就有概率
123456789101112131415161718192021222324252627282930313233343536373839package CS408.CollectionText;import java.util.ArrayList;import java.util.Collections;import java.util.Random;public class Text2 { //班级里有N个学生要求:70%的概率随机到男生,30%的概率随机到女生 public static void main(String[] args) { //创建集合 ...
图
图基本概念
注意:
线性表可以是空表,树可以是空树,但图不可以是空,即v一定是非空集
无向图、有向图
简单图、多重图
简单图
多重图
顶点的度、入度、出度
无向图:顶点v的度是指依附于改顶点的边的条数,极左TD(v)
有向图:
入读是以顶点v为终点的有向边的数目,记为ID(v)
出度是以顶点v为起点的有向边的数目,记为OD(v)
顶点的度等于入度和出度之和,TD(v)=ID(v)+OD(v)
顶点-顶点的关系描述
路径:顶点v1到顶点v2之间的一条路径
回路:第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径:在路径序列中,顶点不重复出现的路径称为简单路径。
简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。
路径长度:路径上边的数目
点到点的距离:从顶点u出发到顶点v的最短路径若存在,则此路径的长度称为从u到v的距离。若从u到v根本不存在路径,则记该距离为无穷
无向图中,若从顶点v到顶点w有路径存在,则称v和w是连通的
有向图中,若从顶点v到顶点w和从顶点w到顶点v之间都有路径,则称这两个顶点是强连通的
几 ...
树
树二叉树
节点的内部结构
平衡二叉树
规则:任意节点左右子树不超过一
平衡二叉树的旋转机制
左旋
右旋
红黑树
红黑树是一种自平衡的二叉查找树,是计算机科学中用到的一种数据结构。
1972年出现,当时被称之为平衡二叉B树。后来,1978年被修改为如今的”红黑树”。
它是一种特殊的二叉查找树,红黑树的每一个节点上都有存储位表示节点的颜色,
每一个节点可以是红或者黑;红黑树不是高度平衡的,它的平衡是通过”红黑规则”进行实现的
红黑规则
每一个节点或是红色的,或者是黑色的
根节点必须是黑色
如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的
如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点;
红黑树添加节点的规则:
添加节点默认是红色(效率高)
更多内容请见 :point_right:链接
从零开始搭建个人博客
从零开始搭建个人博客
我为什么要搭建个人博客?
记录美好生活;
提升自己的技术水平;
空闲时间娱乐;
本博客由Github+Hexo搭建,下面我来介绍我做这个博客的全过程:
注册GitHub
首先进入GitHub官网
点击Sign up
输入你要注册的邮箱、密码
Create account
依次按照github的提示来做,之后就省略,不难。
Git安装步骤
进入Git官网,想、点击Downloads
选择自己的系统
选择自己的适合的版本
( 国内下载的速度慢,有时候还会下载失败,我这里提供Git-2.40.1-64-bit的安装包 )
下载完成打开
鼠标左击出现这种情况就可以了
打开Git Bash,输入git出现这种情况就可以了
绑定GitHub并提交文件
打开Git bash 输入ssh,查看本机是否安装SSH
输入ssh-keygen -t rsa,指定生成秘钥,接着再点击四次回车键,生成两个文件,分别为id_rsa,id_rsa.pub,按照指定的文件位置 ...