JavaScript的排序算法——选择排序

0 人评论
  作者: Avrit   分类:学习   浏览:43

选择排序(Selection Sort)

选择排序是一种排序算法,是一个占用常用内存(In-place)的排序方法。时间复杂度为O(n2)。通常情况下,在处理大型数据的时候,性能要比相似的插入排序低。选择排序因其简单性而著称,并且在某些情况下性能要优于更复杂的算法,尤其是在辅助存储空间有限的情况下。

原理

选择排序的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。

选择排序(Selection Sort)

选择排序(Selection Sort)

复杂度

算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定

ES6实现

function SelectionSort(originalArray) {     const array = [...originalArray];     let len = array.length;     for (let i = 0; i < len - 1; i++) {       let  minIndex = i;         for (let j = i + 1; j < len; j++) {             if (array[j] < array[minIndex]) {                 minIndex = j;             }         }        if (minIndex != i) {            [array[minIndex], array[i]] = [array[i], array[minIndex]]        }     }     return array; } 

参考

维基百科
百度百科

相关阅读

JavaScript的排序算法——冒泡排序
JavaScript的排序算法——选择排序
JavaScript的排序算法——插入排序
JavaScript的排序算法——归并排序
JavaScript的排序算法——快速排序

JavaScript的排序算法——冒泡排序

0 人评论
  作者: Avrit   分类:学习   浏览:48

冒泡排序(Bubble Sort)

冒泡排序,有时也被称做沉降排序,是一种比较简单的排序算法。这种算法的实现是通过遍历要排序的列表,把相邻两个不符合排列规则的数据项交换位置,然后重复遍历列表,直到不再出现需要交换的数据项。当没有数据项需要交换时,则表明该列表已排序。

冒泡排序(Bubble Sort)

复杂度

算法 最好情况 平均情况 最坏情况 空间复杂度 稳定性
冒泡排序 O(n) O(n2) O(n2) O(1) 稳定

ES6实现

  1. 普通版冒泡排序
function BubbleSort(array) {     let len = array.length;     for (let i = 0; i < len; i++) {         for (let j = 0; j < len-i-1; j++) {             if (array[j]> array[j+1]) {                 [array[j],array[j+1]] = [array[j+1],array[j]];             }          
        }  
    }  
    return array; } 
  1. 优化版冒泡排序
function BubbleSort(originalArray) {     const array = [...originalArray];     let swapped;     for (let i = 0; i < array.length; i++) {        swapped = true;        for (let j = 0; j < array.length - i - 1; j++) {            if (array[j] > array[j+1]) {             [array[j],array[j+1]] = [array[j+1],array[j]]             swapped = false;            }        }         if (swapped) {             break;         }     }     return array; } 
https://www.jianshu.com/p/2fd84fadab5f

mongoose --- populate主要操作以及简单和$lookup对比

0 人评论
  作者: Avrit   分类:学习   浏览:48
简单的创建声明三张表:user/department/project

const UserSchema = new mongoose.Schema({
  username: { type: String, required: true },
  password: { type: String, required: true },

阅读全文>>

JS中substr与substring的区别

0 人评论
  作者: Avrit   分类:学习   浏览:41
js中substr和substring都是截取字符串中子串,非常相近,可以有一个或两个参数。

语法:substr(start [,length]) 第一个字符的索引是0,start必选 length可选

   substring(start [, end]) 第一个字符的索引是0,start必选 end可选

相同点:当有一个参数时,两者的功能是一样的,返回从start指定的位置直到字符串结束的子串

var str = "hello Tony";

str.substr(6);  //Tony

str.substring(6); //Tony

 

不同点:有两个参数时

(1)substr(start,length) 返回从start位置开始length长度的子串

“goodboy”.substr(1,6);   //oodboy

【注】当length为0或者负数,返回空字符串

(2)substring(start,end) 返回从start位置开始到end位置的子串(不包含end)

“goodboy”.substring(1,6);  //oodbo

【注】:

(1)substring 方法使用 start 和 end 两者中的较小值作为子字符串的起始点

(2)start 或 end 为 NaN 或者负数,那么将其替换为0

另外:ECMA 并没有对 substr() 进行标准化,所以并不建议使用 substr()

Object.prototype.toString.call()方法

0 人评论
  作者: Avrit   分类:学习   浏览:48

在JavaScript里使用typeof判断数据类型,只能区分基本类型,即:number、string、undefined、boolean、object
对于null、array、function、object来说,使用typeof都会统一返回object字符串。
要想区分对象、数组、函数、单纯使用typeof是不行的。在JS中,可以通过Object.prototype.toString方法,判断某个对象之属于哪种内置类型。
分为null、string、boolean、number、undefined、array、function、object、date、math。

1. 判断基本类型

Object.prototype.toString.call(null); // "[object Null]" Object.prototype.toString.call(undefined); // "[object Undefined]" Object.prototype.toString.call(“abc”);// "[object String]" Object.prototype.toString.call(123);// "[object Number]" Object.prototype.toString.call(true);// "[object Boolean]" 

2. 判断原生引用类型

**函数类型** Function fn(){   console.log(“test”); } Object.prototype.toString.call(fn); // "[object Function]" 
**日期类型** var date = new Date(); Object.prototype.toString.call(date); // "[object Date]" 
**数组类型** var arr = [1,2,3]; Object.prototype.toString.call(arr); // "[object Array]" 
**正则表达式** var reg = /[hbc]at/gi; Object.prototype.toString.call(reg); // "[object RegExp]" 
**自定义类型** function Person(name, age) {     this.name = name;     this.age = age; } var person = new Person("Rose", 18); Object.prototype.toString.call(arr); // "[object Object]" 

无法区分自定义对象类型,自定义类型可以采用instanceof区分

console.log(person instanceof Person); // true 

3.判断原生JSON对象

var isNativeJSON = window.JSON && Object.prototype.toString.call(JSON); console.log(isNativeJSON);//输出结果为”[object JSON]”说明JSON是原生的,否则不是;

Node.js事件循环

0 人评论
  作者: Avrit     浏览:55

什么是事件循环

事件循环允许Node.js执行一些异步非阻塞I/O操作的机制或者策略。

尽管JavaScript是单线程的,所以这些操作都尽量交给操作系统的内核去做。 大多数现代操作系统内核都是多线程的,所以它们可以处理在后台执行的多个操作。当其中一个操作完成时,内核会告诉Node.js,将适当的回调添加到轮询队列中,以便最终执行。

事件循环的6个阶段

当Node.js启动时,会初始化事件循环,然后处理在Node.js里运行的代码,包括各种API的调用,定时器,process.nextTick(),然后运行事件循环机制。

事件循环

6阶段都分别做了什么?

  • timers: setTimeout(),setInterval()在这个阶段被执行
  • pending callbacks: 执行一些系统错误的处理,比如TCP,UDP,Socket错误等等。
  • idle, prepare: only used internally.
  • poll: 轮询阶段,向系统获取新的I/O事件,执行I/O回调。首先会先处理到期的定时器的回调,然后处理poll队列里的回调,直到队列里的回调全部被清空,或者达到一个处理的最大值,如果poll队列不为空且刚好有setImmediate,则停止当前的poll阶段,前往check阶段,执行setImmediate回调。如果没有setImmediate,Node.js会去查看有没有定时器任务到期了,如果有的话,就前往timers阶段,执到期行定时器的回调。
    retrieve new I/O events; execute I/O related callbacks (almost all with the exception of close callbacks, the ones scheduled by timers, and setImmediate()); node will block here when appropriate.
  • check: 执行setImmediate() 回调,且setImmediate只能在check阶段执行。
  • close callbacks: 执行结束的回调。

每个阶段都有一个FIFO回调队列要执行。虽然每个阶段都有其特殊的方式,但通常情况下,当事件循环进入给定阶段时,它将执行特定于该阶段的任何操作,然后在该阶段的队列中执行回调,直到队列耗尽或执行了最大数量的回调。当队列耗尽或达到回调限制时,事件循环将移动到下一个阶段,依此类推。

process.nextTick()

图中没有显示process.nextTick(),尽管它是异步API的一部分。这是因为process.nextTick()在技术上不是事件循环的一部分。 是在任意两个阶段中间,只要有process.nextTick()没有被执行,那么优先执行process.nextTick的回调。

测试代码

const { readFile } = require('fs');const EventEmitter = require('events');class EE extends EventEmitter{}const yy = new EE();
yy.on('event',() => {
    console.log('出大事了!');  //2 })

setTimeout(() => {  //5     console.log('0 毫秒到期执行的定时器回调')
},0)

setTimeout(() => { //     console.log('100 毫秒到期执行的定时器回调')
},100)

setTimeout(() => {  //     console.log('200 毫秒到期执行的定时器回调')
},200)

readFile('./package.json','utf-8',data => {
    console.log('完成文件1读操作的回调');  //7 })

readFile('./task.js','utf-8',data => {
    console.log('完成文件2读操作的回调');  //8 })

setImmediate(() => {
  console.log('immediate 立即回调'); //6 })

process.nextTick(() => { //1     console.log('process 的第一次回调');
})Promise.resolve()
.then(() => {
  yy.emit('event');  
  process.nextTick(() => {
    console.log('process 的第二次回调'); //5   }) 
  console.log('Promise的第一次回调'); //3 }).then(() => {
    console.log('Promise的第2次回调'); //4 })

执行结果是什么?
注:文件1,文件2的大小会影响操作结果。

process 的第一次回调
出大事了!Promise的第一次回调Promise的第2次回调
process 的第二次回调0 毫秒到期执行的定时器回调
immediate 立即回调
完成文件2读操作的回调
完成文件1读操作的回调100 毫秒到期执行的定时器回调200 毫秒到期执行的定时器回调

npm安装包参数配置说明

0 人评论
  作者: Avrit   分类:学习   浏览:45
通过npm install不加--save 和npm install --save一样 
都是局部安装并会把模块自动写入package.json中的dependencies里。

npm install --save 局部安装,并会把模块自动写如入package.json中的dependencies里。

npm install --dev局部安装,并会把模块自动写入package.json中的devDependencies里。

阅读全文>>

CentOS7.5安装nodejs

0 人评论
  作者: Avrit   分类:学习   浏览:37

安装方法1——直接部署

1.首先安装wget

yum install -y wget

如果已经安装了可以跳过该步

阅读全文>>

left join(左关联)、right join(右关联)、inner join(自关联)的区别

0 人评论
  作者: Avrit   分类:学习   浏览:43
left join(左联接) 返回包括左表中的所有记录和右表中关联字段相等的记录 

right join(右联接) 返回包括右表中的所有记录和左表中关联字段相等的记录

inner join(等值连接) 只返回两个表中关联字段相等的行

阅读全文>>

MongoDB aggregate 运用总结

0 人评论
  作者: Avrit   分类:学习   浏览:32

$project:包含、排除、重命名和显示字段

$match:查询,需要同find()一样的参数

$limit:限制结果数量

$skip:忽略结果的数量

$sort:按照给定的字段排序结果

$group:按照给定表达式组合结果

$unwind:分割嵌入数组到自己顶层文件

阅读全文>>