zhehua's note


  • 首页

  • 时光

  • 分类

  • 标签

  • 作品

  • 站点

  • 随想

  • 关于

Prototype和__proto__

发表于 2018-06-06 | 分类于 JAVASCRIPT

1528291176757

上图表明了__proto__和prototype的区别,new Foo()对象的构造函数是Foo(){},那么new Foo()对象的__proto__就是Foo.prototype

口诀:

1.每个对象都具有一个名为__proto__的属性;

2.每个构造函数(构造函数标准为大写开头,如Function(),Object()等等JS中自带的构造函数,以及自己创建的)都具有一个名为prototype的方法(注意:既然是方法,那么就是一个对象(JS中函数同样是对象),所以prototype同样带有__proto__属性);

3.每个对象的__proto__属性指向自身构造函数的prototype;

GitHub被收购

发表于 2018-06-05 | 分类于 新闻

img

微软75亿美元正式收购Github,Github将在微软的带领下会有一个更光明的未来!

排序算法整理

发表于 2018-05-25 | 分类于 算法

前言

  排序一直是算法中的经典和入门,也是一个合格的程序员应该随手都能够回答的问题。但是现实是,不经常写,不经常用的话,要是一下子让写或者让讲,估计有一半的人会呛住。

  在前年求职之前,系统的复习过所有经典的排序算法,也可以做到随手写出来的地步,但是前几天接触,突然发现自己都忘的差不多了,可能随手可以写个,选择,冒泡,插入排序,但是堆排(只知道最大堆的特性,基本忘记),快排和归并(只知道思路),所以写这篇文章的目的就是再重新花几天时间系统的再整理一下,复习一下,也以便于后续的温习。

概况

  排序顾名思义就是将一堆杂乱无章的数字,按照一定的规则(最大或者最小)进行排列的过程。

排序的分类

  • 按照是否将所有的记录全部加载到内存中进行排序分为:内部排序和外部排序

    img

  • 按照排序是否稳定分为:稳定排序和不稳定排序

    何谓稳定性?

    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

  • 按照原理可以分为:插入排序,选择排序,交换排序,归并排序和基数排序

排序的方式

  经典的排序算法大致有以下10种

排序方法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 复杂性
直接插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单
希尔排序 O(nlog2n) O(n2) O(n) O(1) 不稳定 较复杂
直接选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 简单
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂
冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定 较复杂
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂
基数排序 O(d(n+r)) O(d(n+r))) O(d(n+r)) O(n+r) 稳定 较复杂

详情

插入排序

概念和原理

插入排序简单的讲就是从一堆无序的数据集中取出一个数,加入到有序的数据集中,直到所有的无序数据集都取完,那么有序的数据集就是排序后的数。

1527263835518

如上图所示,形象的解释了插入排序的原理。开始时,我们的左手为空并且桌子上的牌面向下,然后我们每次从桌子上拿走一张牌并将他们插入到左手中正确的位置,插入排序的原理由此而得。

思想

输入: 数组 A[1….n]

步骤:

​ 使用j作为标志位,j的左边为有序的数字,后边为无序的数字,那么初始j=2,最后n结束;

​ key=A[j]作为待插入的值,假设待加入的值是有序数组中的最大值,那么他的位置应该不变,那么如果不是呢?那么应该从有序数组的最后一个数A[i=j-1](有序数组中的最大值)进行比较,如果小,那么把这个大的数插入到j处,依次直到i>0&key>A[i],继续下一轮。

一句话概括:插入排序就是增熵减熵的过程

伪码
1
2
3
4
5
6
7
8
9
10
INSERTION-SORT(A)
// INSERTION-SORT
for j=2 to A.length
key = A[j]
//insert A[j] into the sorted sequence A[1...j-1]
i = j-1;
while i>0 and A[i]>A[j]
A[i+1] = A[i]
i = i-1
A[i+1] = key
实现

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] insert_sort(int []arrs){
for(int j=1;j<arrs.length;j++){
int key = arrs[j];
int i = j-1;
while(i>=0&&arrs[i]>key){
arrs[i+1] = arrs[i];
i--;
}
arrs[i+1] = key;
}
return arrs;
}

public static void main(String[] args) {
int res[] = new Sort().insert_sort(new int[]{199,1,2,8,3});
for (int e : res) {
System.out.println(e);
}
}

1527412551814

JAVASCRIPT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var insert_sort = function (arrs){
for(var j=1;j<arrs.length;j++){
var key = arrs[j];
var i = j-1;
while(i>=0&&arrs[i]>key){
arrs[i+1] = arrs[i];
i--;
}
arrs[i+1] = key;
}
}
var a = [199,1,2,8,3];
insert_sort(a)
console.log(a) //1,2,3,8,199

时间复杂度

//todo

空间复杂度

//todo

稳定性

//todo

希尔排序

选择排序

概念和原理

选择排序就是就是从一堆数字中取出一个最小的放在一边,然后再去取一个最小的数,跟刚刚取出来的数字放一起,这样直到这堆数字被取完位置。

形象一点比如皇帝翻牌:heart_eyes_cat:,皇帝一天公务繁忙,晚上到了,这个时候太监就会走过来拿着下面的牌子让他选,这个是否皇帝会看一下都有哪些牌子,然后选择他最喜欢的一个妃子;如果皇帝觉得今天一个不够,还需要一个那么皇帝会在剩下的当中选择在他心中地位其次的妃子。

这个时候老佛爷说,皇帝你再选一个,这个时候皇帝又会在剩下的当中选择一个最好的。

1527414146675

皇帝选秀就是一个典型的选择排序问题

  现实生活中选择排序的思想运用的很多:挑衣服,挑零食等等,感觉选择排序的思想有点像贪心算法。

思路

1527413889306

该图阐述了选择排序的思想,从数组中遍历求出最小值,然后与连续的数组开头的组相互调换,直到所有的数都有序,排序结束

伪码
1
2
3
4
5
6
7
8
9
10
SELECTION-SORT(A)                        
for j = 1 to Length(A)
i = j
key = A(i)
for i to Lenth(A)
if key>A(i)
key = A(i) //当前最小值
k = i // 当前最小值的坐标
A(k) = A(j) //把游标位置的数放到最小值的位置中区
A(j) = key //把最小值放入指定的游标位置
实现

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void select_sort(int[] a) {
if (a == null || a.length <= 0) {
return;
}
for (int i = 0; i < a.length; i++) {
int temp = a[i];
int flag = i; // 将当前下标定义为最小值下标
for (int j = i + 1; j < a.length; j++) {
if (a[j] < temp) {// a[j] < temp 从小到大排序;a[j] > temp 从大到小排序
temp = a[j];
flag = j; // 如果有小于当前最小值的关键字将此关键字的下标赋值给flag
}
}
if (flag != i) {
a[flag] = a[i];
a[i] = temp;
}
}
}

public static void main(String[] args) {
int res[] = new int[] { 199, 1, 2, 8, 3 }; // 1,2,3,8,199
new Sort().select_sort(res);
for (int e : res) {
System.out.println(e);
}
}

JAVASCRIPT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var select_sort = function(arrs) {
if (arrs == null || arrs.length <= 0) {
return;
}
for (var i = 0; i < arrs.length; i++) {
var temp = arrs[i];
var flag = i; // 将当前下标定义为最小值下标
for (var j = i + 1; j < arrs.length; j++) {
if (a[j] < temp) {// a[j] < temp 从小到大排序;a[j] > temp 从大到小排序
temp = a[j];
flag = j; // 如果有小于当前最小值的关键字将此关键字的下标赋值给flag
}
}
if (flag != i) {
a[flag] = a[i];
a[i] = temp;
}
}
}
var a = [199,1,2,8,3]; // 1,2,3,8,199
select_sort(a)
console.log(a)
时间复杂度

选择排序交换此处是处于0-(n-1)次之间,需要比较n(n-1) / 2次,赋值操作次数在0-3(n-1)次之间,因此平均时间复杂度为O(n2)

空间复杂度

O(1)

稳定性

序列{5 8 5 2 9}, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法

注:一般认为选择排序是不稳定排序,但是如果开辟一个新数组的话可以保证稳定性

冒泡排序

概念与原理

​ 冒泡的核心是一次bubble的过程,如下图所示,数组A[1…n]进过n-1次bubble过程就可以完成排序。

1527419114353

图中描述的是一次气泡(bubble)过程,小气泡12与相邻的对比,如果自己小,那么向上冒泡,一次冒泡过程就可以把最小的数冒泡到最上层。其余的无序数组也是利用类似的思想进行排序

伪码
1
2
3
4
5
BUBBLESORT(A)  
for i = 1 to A.length-1 //总共bubble n-1次
for j = A.length downto i + 1 //bubble的范围
if A[j] < A[j - 1]
exchange A[j] with A[j - 1] //bubble的过程
实现

JAVA

1
2
3
4
5
6
7
8
9
10
11
public void bubble_sort(int []a){
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-1-i;j++){
if(a[j+1]<a[j]){
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}

JAVASCRIPT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var bubble_sort = function(a){
for(var i=0;i<a.length-1;i++){
for(var j=0;j<a.length-1-i;j++){
if(a[j+1]<a[j]){
var temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
var arrs = [76,18,99,35,12];
bubble_sort(arrs);
console.log(arrs);//12,18,35,76,99
时间复杂度

1527425711208

摘自百度百科

空间复杂度

O(1)

稳定性

冒泡排序比较是相邻的两个元素,交换也发生在这两个元素中。如果两个元素相等,不交换;如果两个相等元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

JAVA IO

发表于 2018-05-22 | 分类于 JAVA

img

HTTP的用户认证方式

发表于 2018-05-20 | 分类于 通信

HTTP的用户认证方式

1. Basic认证

1526717218205

  • 步骤一:当请求的资源需要 BASIC 认证时,服务器会随状态码 401 Authorization Required,返回带 WWW-Authenticate 首部字段的响应。该字段内包含认证的方式(BASIC) 及Request-URI 安全域字符串(realm)
  • 步骤二:客户端将用户 ID 及密码发送给服务器,如上图所示
  • 步骤三:对认证信息的正确性进行验证。如验证通过,则返回一条包含 Request-URI 资源的响应

缺点:使用Base64编码,安全性不高,并且认证使用上不够便捷灵活

2. Digest认证

1526717389002

DIGEST 认证提供了高于 BASIC 认证的安全等级,但是和 HTTPS 的客户端认证相比仍旧很弱。DIGEST 认证提供防止密码被窃听的保护机制,但并不存在防止用户伪装的保护机制。

3. SSL认证

SSL 客户端认证采用双因素认证

双因素认证就是指,认证过程中不仅需要用户名,密码这一个因素,还需要申请认证者提供其他持有信息。与其组合使用的认证方式就是双因素认证

第一个认证因素的 SSL 客户端证书用来认证客户端计算机

另一个认证因素的密码则用来确定这是用户本人的行为。

4. 基于表单的认证

4.1 Session 管理及 Cookie 应用

1526718629646

  • 步骤一:客户端发送登录信息:ID和密码,使用Https进行传输保证安全性
  • 步骤二:服务器验证ID和密码,如果认证通过那么创建session,并且把sessionId通过Set-Cookie的形式发送给客户端,为减轻跨站脚本攻击(XSS)造成的损失,建议事先在 Cookie 内加上 httponly 属性
  • 步骤三:客户端获取到set-Cookie的响应头以后,就会将cookie保存在浏览器进程中不同于一般的cookie,会把cookie的信息保存在客户端所在的磁盘中,并且在后续发送的Http请求中都会以key-value

Https协议简介

发表于 2018-05-19 | 分类于 通信

Https = Http+通信加密+证书+完整性保护

1526711621377

如上图所示,Https本质上还是走的Http,Https 并非是应用层的一种新协议。只是 HTTP 通信接口部分用 SSL(Secure Socket Layer)和或者TLS(Transport Layer Security)协议代替而已。

1526712704537

​ HTTP 直接和 TCP 通信;当使用 HTTPS时,则演变成先和 SSL 通信,再由 SSL 和 TCP通信了。

​ 简言之,所谓 HTTPS,其实就是身披 SSL 协议这层外壳的 HTTP,SSL让HTTP通信更安全。

​ 在理解Https中的SSL之前还需要了解通信中的加密方式,一般的加密方式有对称加密和非对称加密两种,即公开秘钥加密(公有秘钥加密)和共享秘钥加密。

公开密钥加密:使用非对称加密,使用一把公有秘钥和一把私有秘钥,发送方使用接收方的公有秘钥进行加密,将密文发给接收方,接收方使用私有秘钥进行解密处理,这个时候不用担心传输信息和私有秘钥的篡改

共享秘钥加密:使用对称加密,发送方和接收方使用同一把秘钥,发送方在发送数据时,需要将秘钥发送给接收方

​ 在Https中,根据上述两种加密的特点,采用混合加密的方式,交换密钥环节使用公开密钥加密方式,之后的建立通信交换报文阶段则使用共享密钥加密方式。

为什么?

因为公开秘钥加密(非对称加密)使用的通信效率低下,但是安全性更高。交换秘钥环节应该使用这种方式,一旦建立连接,那么使用共享秘钥加密(对称加密)的方式,该方式效率相对较高。

在一般的项目中,如果安全性要求不是太高的情况,在基于表单的认证的前提下,使用HTTP也是可以满足要求的。

​ 秘钥是用来保证通信之间传输信息的合法性,那么怎么保证秘钥是合法的,这里就要引入数字证书的概念,数字证书就是第三方机构颁发的能够证明秘钥合法性的“证据”,那么怎么样保证数字证书的合法性呢?

如何保证证书是合法的?

​ 数字证书认证机构颁发的数字证书。通信时,服务器会将这份由数字证书认证机构颁发的公钥证书发送给客户端,以进行公开密钥加密方式通信。公钥证书也可叫做数字证书或直接称为证书。接到证书的客户端可使用数字证书认证机构的公开密钥,对那张证书上的数字签名进行验证,一旦验证通过,客户端便可明确两件事:一,认证服务器的公开密钥的是真实有效的数字证书认证机构。二,服务器的公开密钥是值得信赖的。

1526715535297

上述是Https在初次通信时,客户端与服务器之间的通信步骤。

Visual Studio Code高效开发

发表于 2018-05-03 | 分类于 工具

Visual Studio Code是微软公司也利用Electron做了一个跨平台的编辑器,具有轻量,跨平台,易用性高等特点,我用着感觉非常的方便,下载地址如下:https://code.visualstudio.com/
下面简述vs code的配置:

配置项 值 说明
“files.autoSave” “onFocusChange” 编辑器失去焦点时,自动保存

下面是快捷键的说明:

快捷键名称 说明
「Cmd + Shift + O」 如何查看代码结构

关于响应式设计的思考

发表于 2017-12-11 | 分类于 UI设计

  今天在工作中进行项目显示的时候发现网页的布局不一致。在平时开发的时候我使用的屏幕是1920×1080,而公司投影是1024×768,两者之间相差一半,所以显示的效果差异也比较大,这不得不引起我的思考,所以我先开篇,以后有关于响应式布局的问题都罗列出来,作为自己以后学习的经验。

  1. BootStrap能够解决响应式布局的所有问题么?
  2. 在进行响应式布局设计的时候,应该先从小屏幕开始还是大屏幕?

Hexo 常用命令

发表于 2017-12-09 | 分类于 Hexo

清理hexo:hexo clean
本地预览:hexo s|hexo server
提交到github:hexo d|hexo deploy #在本地提交之前最好先hexo clean

vue-language-server Elements in iteration expect to have 'v-bind:key' directives.问题解决

发表于 2017-12-09 | 分类于 IDE

更改vetur配置 vscode->首选项->设置->搜索(vetur)

1
2
// Validate vue-html in <template> using eslint-plugin-vue
"vetur.validation.template": true,

改为
“vetur.validation.template”: false

1234
ZheHuaXuan

ZheHuaXuan

知足.感恩.幸运

31 日志
19 分类
45 标签
GitHub E-Mail
© 2019 ZheHuaXuan
由 Hexo 个人专属
|
主题 — NexT.Gemini v5.1.3