cute_girl

cute_girl 查看完整档案

上海编辑中华女子学院  |  计算机科学 编辑  |  填写所在公司/组织 123.com 编辑
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

cute_girl 收藏了文章 · 10月27日

手写极简版Promise

极简版Promise 满足的使用方式

  • 生成实例对象的方式:new MyPromise()
  • 通过类直接调用静态方法:MyPromise.resolve(),目前静态方法仅支持resolve & reject

亲测使用OK,欢迎指教,互相学习,github链接,欢迎star。
附赠利用构造函数手写Promise 的方法,github链接


class MyPromise {
  constructor(fn) {
    // 定义Promise 三种状态
      this.states = {
          PENDING: 'PENDING', RESOLVED: 'RESOLVED', REJECTED: 'REJECTED'
      }
      // 定义传递到then的value
      this.value = null
      // 定义当前Promise运行状态
      this.state = this.states.PENDING
      // 定义Promise失败状态的回调函数集合
      this.resolvedCallBacks = []
      // 定义Promise成功状态的回调函数集合
      this.rejectedCallBacks = []
      // 为静态方法定义其内部使用的指向实例的that  
      MyPromise.that = this
      try {
      // 执行 new MyPromise() 内传入的方法
          fn(MyPromise.resolve, MyPromise.reject)
      } catch (error) {
          MyPromise.reject(this.value)
      }
  }
    // 静态resolve方法,MyPromise实例不可访问;
    //支持类MyPromise访问,例:MyPromise.resolve('success').then(e=>e)
  static resolve(value) {
      // 由于静态方法内部的this指向 类 而不是 实例,所以用下面的方法访问实例对象
      const that = MyPromise.that
      // 判断是否是MyPromise实例访问resolve
      const f = that instanceof MyPromise
      // MyPromise实例对象访问resolve
      if (f && that.state == that.states.PENDING) {
          that.state = that.states.RESOLVED
          that.value = value
          that.resolvedCallBacks.map(cb => (that.value = cb(that.value)))
      }
      // MyPromise类访问resolve
      if (!f) {
          const obj = new MyPromise()
          return Object.assign(obj, {
              state: obj.states.RESOLVED,
              value
          })
      }
  }
   // 静态reject方法,MyPromise实例不可访问;
   //支持类MyPromise访问,例:MyPromise.reject('fail').then(e=>e)
  static reject(value) {
      const that = MyPromise.that
      const f = that instanceof MyPromise
      if (f && that.state == that.states.PENDING) {
          that.state = that.states.REJECTED
          that.value = value
          that.rejectedCallBacks.map(cb => (that.value = cb(that.value)))
      }
      if (!f) {
          const obj = new MyPromise()
          return Object.assign(obj, {
              state: obj.states.REJECTED,
              value
          })
      }
  }
  // 定义在MyPromise原型上的then方法
  then(onFulfilled, onRejected) {
      const { PENDING, RESOLVED, REJECTED } = this.states
      const f = typeof onFulfilled == "function" ? onFulfilled : c => c;
      const r =
          typeof onRejected == "function"
              ? onRejected
              : c => {
                  throw c;
              };

      switch (this.state) {
          case PENDING:
              // ‘PENDING’状态下向回调函数集合添加callback
              this.resolvedCallBacks.push(f)
              this.rejectedCallBacks.push(r)
              break;
          case RESOLVED:
              // 将回调函数的返回值赋值给 实例的 value,满足链式调用then方法时传递value
              this.value = f(this.value)
              break;
          case REJECTED:
              // 同上
              this.value = r(this.value)
              break;
          default:
              break;
      }
      // 满足链式调用then,返回MyPromise实例对象
      return this
  }
}

MyPromise.resolve('success').then((e) => {
  console.log(e);
  return e + 1
}).then( res=> {
  console.log(res);
})
new MyPromise(resolve => {
  setTimeout(() => {
      resolve(1);
  }, 2000);
})
  .then(res1 => {
      console.log(res1);
      return 2;
  })
  .then(res2 => console.log(res2 ));
查看原文

cute_girl 关注了用户 · 10月25日

accord @accord

希望遇到一个公司,遇到一个团队,大家都愿意把code当作一种艺术去书写

关注 41

cute_girl 收藏了文章 · 10月23日

前端十大经典算法

个人博客

算法概述

算法分类

十种常见排序算法可以分为两大类:

非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。

线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。

849589-20180402132530342-980121409.png

算法复杂度

849589-20180402133438219-1946132192.png

相关概念

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。

不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。

时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。

空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。

冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 重复步骤1~3,直到排序完成。

1.2 动图演示

849589-20171015223238449-2146169197.gif

1.3 代码实现

function bubbleSort(arr) {

    var len = arr.length;

    for (var i = 0; i < len - 1; i++) {

        for (var j = 0; j < len - 1 - i; j++) {

            if (arr[j] > arr[j+1]) {       // 相邻元素两两对比

                var temp = arr[j+1];       // 元素交换

                arr[j+1] = arr[j];

                arr[j] = temp;

            }

        }

    }

    return arr;

}

选择排序(Selection Sort)

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

  • 初始状态:无序区为R[1..n],有序区为空;
  • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  • n-1趟结束,数组有序化了。

2.2 动图演示

849589-20171015224719590-1433219824.gif  

2.3 代码实现

function selectionSort(arr) {

    var len = arr.length;

    var minIndex, temp;

    for (var i = 0; i < len - 1; i++) {

        minIndex = i;

        for (var j = i + 1; j < len; j++) {

            if (arr[j] < arr[minIndex]) {    // 寻找最小的数

                minIndex = j;                // 将最小数的索引保存

            }

        }

        temp = arr[i];

        arr[i] = arr[minIndex];

        arr[minIndex] = temp;

    }

    return arr;

} 

2.4 算法分析

表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

3.1 算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2~5。

3.2 动图演示

849589-20171015225645277-1151100000.gif

3.2 代码实现

function insertionSort(arr) {

    var len = arr.length;

    var preIndex, current;

    for (var i = 1; i < len; i++) {

        preIndex = i - 1;

        current = arr[i];

        while (preIndex >= 0 && arr[preIndex] > current) {

            arr[preIndex + 1] = arr[preIndex];

            preIndex--;

        }

        arr[preIndex + 1] = current;

    }

    return arr;

}

3.4 算法分析

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

希尔排序(Shell Sort)

1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

  • 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
  • 按增量序列个数k,对序列进行k 趟排序;
  • 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

4.2 动图演示

849589-20180331170017421-364506073.gif

4.3 代码实现

function shellSort(arr) {

    var len = arr.length,

        temp,

        gap = 1;

    while (gap < len / 3) {         // 动态定义间隔序列

        gap = gap * 3 + 1;

    }

    for (gap; gap > 0; gap = Math.floor(gap / 3)) {

        for (var i = gap; i < len; i++) {

            temp = arr[i];

            for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {

                arr[j + gap] = arr[j];

            }

            arr[j + gap] = temp;

        }

    }

    return arr;

}

4.4 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的。 

归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

5.1 算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

849589-20171015230557043-37375010.gif

5.3 代码实现

function mergeSort(arr) { // 采用自上而下的递归方法
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var result = [];
 
    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        }else {
            result.push(right.shift());
        }
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}

5.4 算法分析

归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。

快速排序(Quick Sort)

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

6.1 算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

  • 从数列中挑出一个元素,称为 “基准”(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

6.2 动图演示

849589-20171015230936371-1413523412.gif

6.3 代码实现

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left =typeof left !='number' ? 0 : left,
        right =typeof right !='number' ? len - 1 : right;
 
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}
 
function partition(arr, left ,right) {    // 分区操作
    var pivot = left,                     // 设定基准值(pivot)
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }       
    }
    swap(arr, pivot, index - 1);
    return index-1;
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

堆排序(Heap Sort)

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

7.1 算法描述

  • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
  • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
  • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

7.2 动图演示

849589-20171015231308699-356134237.gif

7.3 代码实现

var len;   // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量
 
function buildMaxHeap(arr) {  // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
 
function heapify(arr, i) {    // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

计数排序(Counting Sort)

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述

  • 找出待排序的数组中最大和最小的元素;
  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
  • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

8.2 动图演示

849589-20171015231740840-6968181.gif

8.3 代码实现

function countingSort(arr, maxValue) {
    var bucket =new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
 
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
 
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
 
    return arr;
}

8.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时,时间复杂度是O(n+k),空间复杂度也是O(n+k),其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。

桶排序(Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。

9.1 算法描述

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。

9.2 图片演示

849589-20171015232107090-1920702011.png

9.3 代码实现

unction bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];               // 输入数据的最小值
      }else if (arr[i] > maxValue) {
          maxValue = arr[i];               // 输入数据的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;           // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets =new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                     // 对每个桶进行排序,这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
 
    return arr;
}

9.4 算法分析

桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序(Radix Sort)

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

10.1 算法描述

  • 取得数组中的最大数,并取得位数;
  • arr为原始数组,从最低位开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

10.2 动图演示

849589-20171015232453668-1397662527.gif

10.3 代码实现

/ LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value =null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) !=null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

10.4 算法分析

基数排序基于分别排序,分别收集,所以是稳定的。但基数排序的性能比桶排序要略差,每一次关键字的桶分配都需要O(n)的时间复杂度,而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2n) ,当然d要远远小于n,因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k),其中k为桶的数量。一般来说n>>k,因此额外空间需要大概n个左右。

查看原文

cute_girl 赞了文章 · 10月23日

前端十大经典算法

个人博客

算法概述

算法分类

十种常见排序算法可以分为两大类:

非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。

线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。

849589-20180402132530342-980121409.png

算法复杂度

849589-20180402133438219-1946132192.png

相关概念

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。

不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。

时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。

空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。

冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

  • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  • 针对所有的元素重复以上的步骤,除了最后一个;
  • 重复步骤1~3,直到排序完成。

1.2 动图演示

849589-20171015223238449-2146169197.gif

1.3 代码实现

function bubbleSort(arr) {

    var len = arr.length;

    for (var i = 0; i < len - 1; i++) {

        for (var j = 0; j < len - 1 - i; j++) {

            if (arr[j] > arr[j+1]) {       // 相邻元素两两对比

                var temp = arr[j+1];       // 元素交换

                arr[j+1] = arr[j];

                arr[j] = temp;

            }

        }

    }

    return arr;

}

选择排序(Selection Sort)

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

  • 初始状态:无序区为R[1..n],有序区为空;
  • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  • n-1趟结束,数组有序化了。

2.2 动图演示

849589-20171015224719590-1433219824.gif  

2.3 代码实现

function selectionSort(arr) {

    var len = arr.length;

    var minIndex, temp;

    for (var i = 0; i < len - 1; i++) {

        minIndex = i;

        for (var j = i + 1; j < len; j++) {

            if (arr[j] < arr[minIndex]) {    // 寻找最小的数

                minIndex = j;                // 将最小数的索引保存

            }

        }

        temp = arr[i];

        arr[i] = arr[minIndex];

        arr[minIndex] = temp;

    }

    return arr;

} 

2.4 算法分析

表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

3.1 算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2~5。

3.2 动图演示

849589-20171015225645277-1151100000.gif

3.2 代码实现

function insertionSort(arr) {

    var len = arr.length;

    var preIndex, current;

    for (var i = 1; i < len; i++) {

        preIndex = i - 1;

        current = arr[i];

        while (preIndex >= 0 && arr[preIndex] > current) {

            arr[preIndex + 1] = arr[preIndex];

            preIndex--;

        }

        arr[preIndex + 1] = current;

    }

    return arr;

}

3.4 算法分析

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

希尔排序(Shell Sort)

1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

  • 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
  • 按增量序列个数k,对序列进行k 趟排序;
  • 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

4.2 动图演示

849589-20180331170017421-364506073.gif

4.3 代码实现

function shellSort(arr) {

    var len = arr.length,

        temp,

        gap = 1;

    while (gap < len / 3) {         // 动态定义间隔序列

        gap = gap * 3 + 1;

    }

    for (gap; gap > 0; gap = Math.floor(gap / 3)) {

        for (var i = gap; i < len; i++) {

            temp = arr[i];

            for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {

                arr[j + gap] = arr[j];

            }

            arr[j + gap] = temp;

        }

    }

    return arr;

}

4.4 算法分析

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版)》的合著者Robert Sedgewick提出的。 

归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

5.1 算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

849589-20171015230557043-37375010.gif

5.3 代码实现

function mergeSort(arr) { // 采用自上而下的递归方法
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var result = [];
 
    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        }else {
            result.push(right.shift());
        }
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}

5.4 算法分析

归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。

快速排序(Quick Sort)

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

6.1 算法描述

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

  • 从数列中挑出一个元素,称为 “基准”(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

6.2 动图演示

849589-20171015230936371-1413523412.gif

6.3 代码实现

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left =typeof left !='number' ? 0 : left,
        right =typeof right !='number' ? len - 1 : right;
 
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}
 
function partition(arr, left ,right) {    // 分区操作
    var pivot = left,                     // 设定基准值(pivot)
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }       
    }
    swap(arr, pivot, index - 1);
    return index-1;
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

堆排序(Heap Sort)

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

7.1 算法描述

  • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
  • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
  • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

7.2 动图演示

849589-20171015231308699-356134237.gif

7.3 代码实现

var len;   // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量
 
function buildMaxHeap(arr) {  // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}
 
function heapify(arr, i) {    // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

计数排序(Counting Sort)

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述

  • 找出待排序的数组中最大和最小的元素;
  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
  • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

8.2 动图演示

849589-20171015231740840-6968181.gif

8.3 代码实现

function countingSort(arr, maxValue) {
    var bucket =new Array(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;
 
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }
 
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
 
    return arr;
}

8.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时,时间复杂度是O(n+k),空间复杂度也是O(n+k),其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。

桶排序(Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。

9.1 算法描述

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。

9.2 图片演示

849589-20171015232107090-1920702011.png

9.3 代码实现

unction bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];               // 输入数据的最小值
      }else if (arr[i] > maxValue) {
          maxValue = arr[i];               // 输入数据的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;           // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets =new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                     // 对每个桶进行排序,这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }
 
    return arr;
}

9.4 算法分析

桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序(Radix Sort)

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

10.1 算法描述

  • 取得数组中的最大数,并取得位数;
  • arr为原始数组,从最低位开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

10.2 动图演示

849589-20171015232453668-1397662527.gif

10.3 代码实现

/ LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value =null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) !=null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

10.4 算法分析

基数排序基于分别排序,分别收集,所以是稳定的。但基数排序的性能比桶排序要略差,每一次关键字的桶分配都需要O(n)的时间复杂度,而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2n) ,当然d要远远小于n,因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k),其中k为桶的数量。一般来说n>>k,因此额外空间需要大概n个左右。

查看原文

赞 191 收藏 149 评论 5

cute_girl 收藏了文章 · 10月23日

js数据结构-二叉树(二叉搜索树)

前言

可能有一部分人没有读过我上一篇写的二叉堆,所以这里把二叉树的基本概念复制过来了,如果读过的人可以忽略前面针对二叉树基本概念的介绍,另外如果对链表数据结构不清楚的最好先看一下本人之前写的js数据结构-链表

二叉树

二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。而每个分支节点也常常被称作为一棵子树。

图片描述

  • 根节点:二叉树最顶层的节点
  • 分支节点:除了根节点以外且拥有叶子节点
  • 叶子节点:除了自身,没有其他子节点

常用术语
在二叉树中,我们常常还会用父节点和子节点来描述,比如图中2为6和3的父节点,反之6和3是2子节点

二叉树的三个性质

  1. 在二叉树的第i层上,至多有2^i-1个节点

    • i=1时,只有一个根节点,2^(i-1) = 2^0 = 1
  2. 深度为k的二叉树至多有2^k-1个节点

    • i=2时,2^k-1 = 2^2 - 1 = 3个节点
  3. 对任何一棵二叉树T,如果总结点数为n0,度为2(子树数目为2)的节点数为n2,则n0=n2+1

树和二叉树的三个主要差别

  • 树的节点个数至少为1,而二叉树的节点个数可以为0
  • 树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为2
  • 树的节点没有左右之分,而二叉树的节点有左右之分

二叉树分类

二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)

  • 满二叉树:一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树
  • 完全二叉树:完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

图片描述

二叉搜索树

二叉搜索树满足以下的几个性质:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 任意节点的左、右子树也需要满足左边小右边大的性质

我们来举个例子来深入理解以下

一组数据:12,4,18,1,8,16,20
由下图可以看出,左边的图满足了二叉树的性质,它的每个左子节点都小于父节点,右子节点大于其父节点,同时左子树的节点都小于根节点,右子树的节点都大于根节点

图片描述

二叉搜索树主要的几个操作:

  • 查找(search)
  • 插入(insert)
  • 遍历(transverse)

二叉树搜索树的链式存储结构

通过下图,可以知道二叉搜索树的节点通常包含4个域,数据元素,分别指向其左,右节点的指针和一个指向父节点的指针所构成,一般把这种存储结构称为三叉链表。
图片描述

用代码初始化一个二叉搜索树的结点:

  • 一个指向父亲节点的指针 parent
  • 一个指向左节点的指针 left
  • 一个指向右节点的指针 right
  • 一个数据元素,里面可以是一个key和value
    class BinaryTreeNode {
        constructor(key, value){
            this.parent = null;
            this.left = null;
            this.right = null;
            this.key = key;
            this.value = value;
        }
    }

接着我们再用代码去初始化一个二叉搜索树

  • 在二叉搜索树中我们会维护一个root指针,这个就相当于链表中的head指针,在没有任何节点插入的时候它指向空,在有节点插入以后它指向根节点。
    class BinarySearchTree {
        constructor() {
            this.root = null;
        }
    }

创建节点

    static createNode(key, value) {
        return new BinarySearchTree(key, value);
    }

插入操作

看下面这张图,13是我们要插入的节点,它插入的具体步骤:

  1. 跟根节点12做比较,比12大,所以我们确定了,这个节点是往右子树插入的
  2. 而根节点的右边已经有节点,那么跟这个节点18做比较,结果小于18所以往18的左节点找位置
  3. 而18的左节点也已经有节点了,所以继续跟这个节点做比较,结果小于16
  4. 刚好16的左节点是空的(left=null),所以13这个节点就插入到了16的左节点

图片描述

通过上面的描述,我们来看看代码是怎么写的

  • 定义两个指针,分别是p和tail,最初都指向root,p是用来指向要插入的位置的父节点的指针,而tail是用来查找插入位置的,所以最后它会指向null,用上图举个例子,p最后指向了6这个节点,而tail最后指向了null(tail为null则说明已经找到了要插入的位置)
  • 循环,tail根据我们上面分析的一步一步往下找位置插入,如果比当前节点小就往左找,大则往右找,一直到tail找到一个空位置也就是null
  • 如果当前的root为null,则说明当前结构中并没有节点,所以插入的第一个节点直接为跟节点,即this.root = node
  • 将插入后的节点的parent指针指向父节点
    insert(node){
        let p = this.root;
        let tail = this.root;
        
        // 循环遍历,去找到对应的位置
        while(tail) {
            p = tail;
            // 要插入的节点key比当前节点小
            if (node.key < tail.key){
                tail = tail.left;
            }
            // 要插入的节点key比当前节点大
            else {
                tail = tail.right;
            }
        }
        
        // 没有根节点,则直接作为根节点插入
        if(!p) {
            this.root = node;
            return;
        }
        
        // p是最后一个节点,也就是我们要插入的位置的父节点
        // 比父节点大则往右边插入
        if(p.key < node.key){
            p.right = node;
        }
        // 比父节点小则往左边插入
        else {
            p.left = node;
        }
        
        // 指向父节点
        node.parent = p;

    }

查找

查找就很简单了,其实和插入差多,都是去别叫左右节点的大小,然后往下找

  • 如果root = null, 则二叉树中没有任何节点,直接return,或者报个错什么的。
  • 循环查找
    search(key) {
        let p = this.root;
        if(!p) {
            return;
        }
        
        while(p && p.key !== key){
            if(p.key<key){
                p = p.right;
            }else{
                p = p.left;
            }
        }
        
        return p;
    }

遍历

  • 中序遍历(inorder):先遍历左节点,再遍历自己,最后遍历右节点,输出的刚好是有序的列表
  • 前序遍历(preorder):先自己,再遍历左节点,最后遍历右节点
  • 后序遍历(postorder):先左节点,再右节点,最后自己

最常用的一般是中序遍历,因为中序遍历可以得到一个已经排好序的列表,这也是为什么会用二叉搜索树排序的原因

根据上面对中序遍历的解释,那么代码就变的很简单,就是一个递归的过程,递归停止的条件就是节点为null

  • 先遍历左节点-->yield* this._transverse(node.left)
  • 遍历自己 --> yield* node
  • 遍历左节点 --> yield* this._transverse(node.right)
    transverse() {
        return this._transverse(this.root);
    }
    
    *_transverse(node){
        if(!node){
            return;
        }
        yield* this._transverse(node.left);
        yield node;
        yield* this._transverse(node.right)
    }

图片描述
看上面这张图,我们简化的来看一下,先访问左节点4,再自己12,然后右节点18,这样输出的就刚好是一个4,12,18

补充:这个地方用了generater,所以返回的一个迭代器。可以通过下面这种方式得到一个有序的数组,这里的前提就当是已经有插入的节点了

   const tree = new BinaryTree();
   //...中间省略插入过程
    
   // 这样就返回了一个有序的数组 
   var arr = [...tree.transverse()].map(item=>item.key);

完整代码

class BinaryTreeNode {
  constructor(key, value) {
    // 指向父节点
    this.p = null;

    // 左节点
    this.left = null;

    // 右节点
    this.right = null;

    // 键
    this.key = key;

    // 值
    this.value = value;
  }
}

class BinaryTree {
  constructor() {
    this.root = null;
  }

  static createNode(key, value) {
    return new BinaryTreeNode(key, value);
  }

  search(key) {
    let p = this.root;
    if (!p) {
      return;
    }

    while (p && p.key !== key) {
      if (p.key < key) {
        p = p.right;
      } else {
        p = p.left;
      }
    }

    return p;
  }

  insert(node) {
    // 尾指针的父节点指针
    let p = this.root;

    // 尾指针
    let tail = this.root;

    while (tail) {
      p = tail;
      if (node.key < tail.key) {
        tail = tail.left;
      } else {
        tail = tail.right;
      }
    }

    if (!p) {
      this.root = node;
      return;
    }

    // 插入
    if (p.key < node.key) {
      p.right = node;
    } else {
      p.left = node;
    }

    node.p = p;
  }

  transverse() {
    return this.__transverse(this.root);
  }

  *__transverse(node) {
    if (!node) {
      return;
    }
    yield* this.__transverse(node.left);
    yield node;
    yield* this.__transverse(node.right);
  }
}

总结

二叉查找树就讲完了哈,其实这个和链表很像的,还是操作那么几个指针,既然叫查找树了,它主要还是用来左一些搜索,还有就是排序了,另外补充一下,二叉查找树里找最大值和最小值也很方便是不是,如果你大致读懂了的话。
这篇文章我写的感觉有点乱诶,因为总感觉哪里介绍的不到位,让一些基础差的人会看不懂,如果有不懂或者文章哪里写错了,欢迎评论留言哈

后续

后续写什么呢,这个问题我也在想,排序算法,react第三方的一些模拟实现?,做个小程序组件库?还是别的,容我再想几个小时,因为可以,有建议的朋友们也可以留言说一下哈。
最后最后,最重要的请给个赞,请粉一个呢,谢谢啦

查看原文

cute_girl 收藏了文章 · 10月20日

tsconfig.json配置详解

前言

由于开发ts的项目经常要配置tsconfig.json,所以自己整理了一份tsconfig.json文件,方便以后查阅~
cmd-markdown-logo

compilerOptions编译选项

target用于指定编译之后的版本目录

"target": "es5",  

module用来指定要使用的模板标准

"module": "commonjs", 

lib用于指定要包含在编译中的库文件

"lib":[
  "es6",
  "dom"
],

allowJs用来指定是否允许编译JS文件,默认false,即不编译JS文件

"allowJs": true,

checkJs用来指定是否检查和报告JS文件中的错误,默认false

"checkJs": true, 

指定jsx代码用于的开发环境:'preserve','react-native',or 'react

"jsx": "preserve", 

declaration用来指定是否在编译的时候生成相的d.ts声明文件,如果设为true,编译每个ts文件之后会生成一个js文件和一个声明文件,但是declaration和allowJs不能同时设为true

"declaration": true,

declarationMap用来指定编译时是否生成.map文件

"declarationMap": true,

socuceMap用来指定编译时是否生成.map文件

"sourceMap": true,

outFile用于指定输出文件合并为一个文件,只有设置module的值为amd和system模块时才支持这个配置

"outFile": "./",

outDir用来指定输出文件夹,值为一个文件夹路径字符串,输出的文件都将放置在这个文件夹

"outDir": "./",

rootDir用来指定编译文件的根目录,编译器会在根目录查找入口文件

"rootDir": "./",

composite是否编译构建引用项目

"composite": true, 

removeComments用于指定是否将编译后的文件注释删掉,设为true的话即删除注释,默认为false

"removeComments": true,

noEmit不生成编译文件

"noEmit": true, 

importHelpers指定是否引入tslib里的复制工具函数,默认为false

"importHelpers": true,

当target为"ES5"或"ES3"时,为"for-of" "spread"和"destructuring"中的迭代器提供完全支持

"downlevelIteration": true, 

isolatedModules指定是否将每个文件作为单独的模块,默认为true,他不可以和declaration同时设定

"isolatedModules": true,

strict用于指定是否启动所有类型检查,如果设为true这回同时开启下面这几个严格检查,默认为false

"strict": true,

noImplicitAny如果我们没有一些值设置明确类型,编译器会默认认为这个值为any类型,如果将noImplicitAny设为true,则如果没有设置明确的类型会报错,默认值为false

"noImplicitAny": true,

strictNullChecks当设为true时,null和undefined值不能赋值给非这两种类型的值,别的类型的值也不能赋给他们,除了any类型,还有个例外就是undefined可以赋值给void类型

"strictNullChecks": true,

strictFunctionTypes用来指定是否使用函数参数双向协变检查

"strictFunctionTypes": true,

strictBindCallApply设为true后对bind、call和apply绑定的方法的参数的检测是严格检测

"strictBindCallApply": true,

strictPropertyInitialization设为true后会检查类的非undefined属性是否已经在构造函数里初始化,如果要开启这项,需要同时开启strictNullChecks,默认为false

"strictPropertyInitialization": true,

当this表达式的值为any类型的时候,生成一个错误

"noImplicitThis": true,

alwaysStrict指定始终以严格模式检查每个模块,并且在编译之后的JS文件中加入"use strict"字符串,用来告诉浏览器该JS为严格模式

"alwaysStrict": true,  

noUnusedLocals用于检查是否有定义了但是没有使用变量,对于这一点的检测,使用ESLint可以在你书写代码的时候做提示,你可以配合使用,他的默认值为false

"noUnusedLocals": true, 

noUnusedParameters用于检测是否在函数中没有使用的参数

"noUnusedParameters": true,

noImplicitReturns用于检查函数是否有返回值,设为true后,如果函数没有返回值则会提示,默认为false

"noImplicitReturns": true,

noFallthroughCasesInSwitch用于检查switch中是否有case没有使用break跳出switch,默认为false

"noFallthroughCasesInSwitch": true, 

moduleResolution用于选择模块解析策略,有"node"和"classic"两种类型

"moduleResolution": "node",

baseUrl用于设置解析非相对模块名称的基本目录,相对模块不会受到baseUrl的影响

"baseUrl": "./", 

paths用于设置模块名到基于baseUrl的路径映射

  "paths": {
      "*":["./node_modules/@types", "./typings/*"]
    },

rootDirs可以指定一个路径列表,在构建时编译器会将这个路径中的内容都放到一个文件夹中

"rootDirs": [], 

typeRoots用来指定声明文件或文件夹的路径列表,如果指定了此项,则只有在这里列出的声明文件才会被加载

"typeRoots": [],

types用于指定需要包含的模块,只有在这里列出的模块的声明文件才会被加载

"types": [], 

allowSyntheticDefaultImports用来指定允许从没有默认导出的模块中默认导入

"allowSyntheticDefaultImports": true,

esModuleInterop通过导入内容创建命名空间,实现CommonJS和ES模块之间的互操作性

"esModuleInterop": true, 

不把符号链接解析为真实路径,具体可以了解下webpack和node.js的symlink相关知识

"preserveSymlinks": true,  

sourceRoot用于指定调试器应该找到TypeScript文件而不是源文件的位置,这个值会被写进.map文件里

"sourceRoot": "", 

mapRoot用于指定调试器找到映射文件而非生成文件的位置,指定map文件的根路径,该选项会影响.map文件中的sources属性

"mapRoot": "",

inlineSourceMap指定是否将map文件内容和js文件编译在一个同一个js文件中,如果设为true,则map的内容会以//#soureMappingURL=开头,然后接base64字符串的形式插入在js文件底部

"inlineSourceMap": true, 

inlineSources用于指定是否进一步将ts文件的内容也包含到输出文件中

"inlineSources": true, 

experimentalDecorators用于指定是否启用实验性的装饰器特性

"experimentalDecorators": true,

emitDecoratorMetadata用于指定是否为装上去提供元数据支持,关于元数据,也是ES6的新标准,可以通过Reflect提供的静态方法获取元数据,如果需要使用Reflect的一些方法,需要引用ES2015.Reflect这个库

"emitDecoratorMetadata": true,

include也可以指定要编译的路径列表

"include":[],

files可以配置一个数组列表

 "files":[],

exclude表示要排除的,不编译的文件,它也可以指定一个列表,规则和include一样,可以是文件可以是文件夹,可以是相对路径或绝对路径,可以使用通配符

"exclude":[]

extends可以通过指定一个其他的tsconfig.json文件路径,来继承这个配置文件里的配置,继承来的文件的配置会覆盖当前文件定义的配置

"extends":""

compileOnSave如果设为true,在我们编辑了项目文件保存的时候,编辑器会根据tsconfig.json的配置更新重新生成文本,不过这个编辑器支持

"compileOnSave":true

一个对象数组,指定要引用的项目

"references":[]

最后

如果本文对你有帮助得话,给本文点个赞❤️❤️❤️

欢迎大家加入,一起学习前端,共同进步!
cmd-markdown-logo

查看原文

cute_girl 赞了文章 · 10月20日

tsconfig.json配置详解

前言

由于开发ts的项目经常要配置tsconfig.json,所以自己整理了一份tsconfig.json文件,方便以后查阅~
cmd-markdown-logo

compilerOptions编译选项

target用于指定编译之后的版本目录

"target": "es5",  

module用来指定要使用的模板标准

"module": "commonjs", 

lib用于指定要包含在编译中的库文件

"lib":[
  "es6",
  "dom"
],

allowJs用来指定是否允许编译JS文件,默认false,即不编译JS文件

"allowJs": true,

checkJs用来指定是否检查和报告JS文件中的错误,默认false

"checkJs": true, 

指定jsx代码用于的开发环境:'preserve','react-native',or 'react

"jsx": "preserve", 

declaration用来指定是否在编译的时候生成相的d.ts声明文件,如果设为true,编译每个ts文件之后会生成一个js文件和一个声明文件,但是declaration和allowJs不能同时设为true

"declaration": true,

declarationMap用来指定编译时是否生成.map文件

"declarationMap": true,

socuceMap用来指定编译时是否生成.map文件

"sourceMap": true,

outFile用于指定输出文件合并为一个文件,只有设置module的值为amd和system模块时才支持这个配置

"outFile": "./",

outDir用来指定输出文件夹,值为一个文件夹路径字符串,输出的文件都将放置在这个文件夹

"outDir": "./",

rootDir用来指定编译文件的根目录,编译器会在根目录查找入口文件

"rootDir": "./",

composite是否编译构建引用项目

"composite": true, 

removeComments用于指定是否将编译后的文件注释删掉,设为true的话即删除注释,默认为false

"removeComments": true,

noEmit不生成编译文件

"noEmit": true, 

importHelpers指定是否引入tslib里的复制工具函数,默认为false

"importHelpers": true,

当target为"ES5"或"ES3"时,为"for-of" "spread"和"destructuring"中的迭代器提供完全支持

"downlevelIteration": true, 

isolatedModules指定是否将每个文件作为单独的模块,默认为true,他不可以和declaration同时设定

"isolatedModules": true,

strict用于指定是否启动所有类型检查,如果设为true这回同时开启下面这几个严格检查,默认为false

"strict": true,

noImplicitAny如果我们没有一些值设置明确类型,编译器会默认认为这个值为any类型,如果将noImplicitAny设为true,则如果没有设置明确的类型会报错,默认值为false

"noImplicitAny": true,

strictNullChecks当设为true时,null和undefined值不能赋值给非这两种类型的值,别的类型的值也不能赋给他们,除了any类型,还有个例外就是undefined可以赋值给void类型

"strictNullChecks": true,

strictFunctionTypes用来指定是否使用函数参数双向协变检查

"strictFunctionTypes": true,

strictBindCallApply设为true后对bind、call和apply绑定的方法的参数的检测是严格检测

"strictBindCallApply": true,

strictPropertyInitialization设为true后会检查类的非undefined属性是否已经在构造函数里初始化,如果要开启这项,需要同时开启strictNullChecks,默认为false

"strictPropertyInitialization": true,

当this表达式的值为any类型的时候,生成一个错误

"noImplicitThis": true,

alwaysStrict指定始终以严格模式检查每个模块,并且在编译之后的JS文件中加入"use strict"字符串,用来告诉浏览器该JS为严格模式

"alwaysStrict": true,  

noUnusedLocals用于检查是否有定义了但是没有使用变量,对于这一点的检测,使用ESLint可以在你书写代码的时候做提示,你可以配合使用,他的默认值为false

"noUnusedLocals": true, 

noUnusedParameters用于检测是否在函数中没有使用的参数

"noUnusedParameters": true,

noImplicitReturns用于检查函数是否有返回值,设为true后,如果函数没有返回值则会提示,默认为false

"noImplicitReturns": true,

noFallthroughCasesInSwitch用于检查switch中是否有case没有使用break跳出switch,默认为false

"noFallthroughCasesInSwitch": true, 

moduleResolution用于选择模块解析策略,有"node"和"classic"两种类型

"moduleResolution": "node",

baseUrl用于设置解析非相对模块名称的基本目录,相对模块不会受到baseUrl的影响

"baseUrl": "./", 

paths用于设置模块名到基于baseUrl的路径映射

  "paths": {
      "*":["./node_modules/@types", "./typings/*"]
    },

rootDirs可以指定一个路径列表,在构建时编译器会将这个路径中的内容都放到一个文件夹中

"rootDirs": [], 

typeRoots用来指定声明文件或文件夹的路径列表,如果指定了此项,则只有在这里列出的声明文件才会被加载

"typeRoots": [],

types用于指定需要包含的模块,只有在这里列出的模块的声明文件才会被加载

"types": [], 

allowSyntheticDefaultImports用来指定允许从没有默认导出的模块中默认导入

"allowSyntheticDefaultImports": true,

esModuleInterop通过导入内容创建命名空间,实现CommonJS和ES模块之间的互操作性

"esModuleInterop": true, 

不把符号链接解析为真实路径,具体可以了解下webpack和node.js的symlink相关知识

"preserveSymlinks": true,  

sourceRoot用于指定调试器应该找到TypeScript文件而不是源文件的位置,这个值会被写进.map文件里

"sourceRoot": "", 

mapRoot用于指定调试器找到映射文件而非生成文件的位置,指定map文件的根路径,该选项会影响.map文件中的sources属性

"mapRoot": "",

inlineSourceMap指定是否将map文件内容和js文件编译在一个同一个js文件中,如果设为true,则map的内容会以//#soureMappingURL=开头,然后接base64字符串的形式插入在js文件底部

"inlineSourceMap": true, 

inlineSources用于指定是否进一步将ts文件的内容也包含到输出文件中

"inlineSources": true, 

experimentalDecorators用于指定是否启用实验性的装饰器特性

"experimentalDecorators": true,

emitDecoratorMetadata用于指定是否为装上去提供元数据支持,关于元数据,也是ES6的新标准,可以通过Reflect提供的静态方法获取元数据,如果需要使用Reflect的一些方法,需要引用ES2015.Reflect这个库

"emitDecoratorMetadata": true,

include也可以指定要编译的路径列表

"include":[],

files可以配置一个数组列表

 "files":[],

exclude表示要排除的,不编译的文件,它也可以指定一个列表,规则和include一样,可以是文件可以是文件夹,可以是相对路径或绝对路径,可以使用通配符

"exclude":[]

extends可以通过指定一个其他的tsconfig.json文件路径,来继承这个配置文件里的配置,继承来的文件的配置会覆盖当前文件定义的配置

"extends":""

compileOnSave如果设为true,在我们编辑了项目文件保存的时候,编辑器会根据tsconfig.json的配置更新重新生成文本,不过这个编辑器支持

"compileOnSave":true

一个对象数组,指定要引用的项目

"references":[]

最后

如果本文对你有帮助得话,给本文点个赞❤️❤️❤️

欢迎大家加入,一起学习前端,共同进步!
cmd-markdown-logo

查看原文

赞 27 收藏 22 评论 0

cute_girl 赞了文章 · 10月16日

JS -- sort()方法实现对象数组的排序

sort()方法会改变原数组,默认按unicode码顺序排列

我们通常遇到的都是数组排序,对于对象数组当然也是可以的,方法如下:

对象数组排序

可以选择它的某一属性进行比较

var arr = [
            { name:"小明", age:12 },
            { name:"小红", age:11 },
            { name:"小刚", age:15 },
            { name:"小华", age:13 }
        ];
        
function compare(p){ //这是比较函数
    return function(m,n){
        var a = m[p];
        var b = n[p];
        return a - b; //升序
    }
}
arr.sort(compare("age"));
console.log(arr); 
//结果如下: 
//[{name: "小红", age: 11}, 
//{name: "小明", age: 12},
//{name: "小华", age: 13}, 
//{name: "小刚", age: 15}]

数组排序

不使用比较函数会出现下面这种情况,这并不是我们需要的结果

var arr = [2,3,13,17,4,19,1];
arr.sort() // 结果:[1, 13, 17, 19, 2, 3, 4]

若想对数组按照大小进行排序,则需要在sort()方法中添加比较函数

var arr = [2,3,13,17,4,19,1];
arr.sort(function(a,b){ // 这是比较函数
    return b - a;    // 降序
})
console.log(arr) // 结果:[19, 17, 13, 4, 3, 2, 1]
查看原文

赞 8 收藏 3 评论 4

cute_girl 提出了问题 · 9月30日

antd v4版本Table虚拟列表组件 这段代码的作用是什么

虚拟列表

Object.defineProperty(obj, 'scrollLeft', {
        get: () => null,
        set: scrollLeft => {
            if (gridRef.current) {
                gridRef.current.scrollTo({
                    scrollLeft
                });
            }
        }
    });

官方解释是:“Table 标题滚动的时候,同步 Grid 滚动”

但我删除这段代码Table也能正常运行,求解

关注 1 回答 0

cute_girl 收藏了文章 · 9月1日

你不知道的 useCallback

欢迎关注我的公众号睿Talk,获取我最新的文章:
clipboard.png

一、前言

对于新手来说,没写过几次死循环的代码都不好意思说自己用过 React Hooks。本文将以useCallback为切入点,谈谈几个 hook 的使用场景,以及性能优化的一些思考。

这算是 Hooks 系列的第 3 篇,之前 2 篇的传送门:
React Hooks 解析(上):基础
React Hooks 解析(下):进阶

二、useCallback 使用场景

先看一个最简单的例子:

// 用于记录 getData 调用次数
let count = 0;

function App() {
  const [val, setVal] = useState("");

  function getData() {
    setTimeout(()=>{
      setVal('new data '+count);
      count++;
    }, 500)
  }

  useEffect(()=>{
    getData();
  }, []);

  return (
    <div>{val}</div>
  );
}

getData模拟发起网络请求。在这种场景下,没有useCallback什么事,组件本身是高内聚的。

如果涉及到组件通讯,情况就不一样了:

// 用于记录 getData 调用次数
let count = 0;

function App() {
  const [val, setVal] = useState("");

  function getData() {
    setTimeout(() => {
      setVal("new data " + count);
      count++;
    }, 500);
  }

  return <Child val={val} getData={getData} />;
}

function Child({val, getData}) {
  useEffect(() => {
    getData();
  }, [getData]);

  return <div>{val}</div>;
}

就这么轻轻松松,一个死循环就诞生了...

先来分析下这段代码的用意,Child组件是一个纯展示型组件,其业务逻辑都是通过外部传进来的,这种场景在实际开发中很常见。

再分析下代码的执行过程:

  1. App渲染Child,将valgetData传进去
  2. Child使用useEffect获取数据。因为对getData有依赖,于是将其加入依赖列表
  3. getData执行时,调用setVal,导致App重新渲染
  4. App重新渲染时生成新的getData方法,传给Child
  5. Child发现getData的引用变了,又会执行getData
  6. 3 -> 5 是一个死循环

如果明确getData只会执行一次,最简单的方式当然是将其从依赖列表中删除。但如果装了 hook 的lint 插件,会提示:React Hook useEffect has a missing dependency

useEffect(() => {
  getData();
}, []);

实际情况很可能是当getData改变的时候,是需要重新获取数据的。这时就需要通过useCallback来将引用固定住:

const getData = useCallback(() => {
  setTimeout(() => {
    setVal("new data " + count);
    count++;
  }, 500);
}, []);

上面例子中getData的引用永远不会变,因为他它的依赖列表是空。可以根据实际情况将依赖加进去,就能确保依赖不变的情况下,函数的引用保持不变。

三、useCallback 依赖 state

假如在getData中需要用到val( useState 中的值),就需要将其加入依赖列表,这样的话又会导致每次getData的引用都不一样,死循环又出现了...

const getData = useCallback(() => {
  console.log(val);

  setTimeout(() => {
    setVal("new data " + count);
    count++;
  }, 500);
}, [val]);

如果我们希望无论val怎么变,getData的引用都保持不变,同时又能取到val最新的值,可以通过自定义 hook 实现。注意这里不能简单的把val从依赖列表中去掉,否则getData中的val永远都只会是初始值(闭包原理)。

function useRefCallback(fn, dependencies) {
  const ref = useRef(fn);

  // 每次调用的时候,fn 都是一个全新的函数,函数中的变量有自己的作用域
  // 当依赖改变的时候,传入的 fn 中的依赖值也会更新,这时更新 ref 的指向为新传入的 fn
  useEffect(() => {
    ref.current = fn;
  }, [fn, ...dependencies]);

  return useCallback(() => {
    const fn = ref.current;
    return fn();
  }, [ref]);
}

使用:

const getData = useRefCallback(() => {
  console.log(val);

  setTimeout(() => {
    setVal("new data " + count);
    count++;
  }, 500);
}, [val]);

完整代码可以看这里

四、性能

一般会觉得使用useCallback的性能会比普通重新定义函数的性能好, 如下面例子:

function App() {
  const [val, setVal] = useState("");

  const onChange = (evt) => {
    setVal(evt.target.value);
  };

  return <input val={val} onChange={onChange} />;
}

onChange改为:

const onChange = useCallback(evt => {
  setVal(evt.target.value);
}, []);

实际性能会更差,可以在这里自行测试。究其原因,上面的写法几乎等同于下面:

const temp = evt => {
  setVal(evt.target.value);
};

const onChange = useCallback(temp, []);

可以看到onChange的定义是省不了的,而且额外还要加上调用useCallback产生的开销,性能怎么可能会更好?

真正有助于性能改善的,有 2 种场景:

  • 函数定义时需要进行大量运算, 这种场景极少
  • 需要比较引用的场景,如上文提到的useEffect,又或者是配合React.Memo使用:
const Child = React.memo(function({val, onChange}) {
  console.log('render...');
  
  return <input value={val} onChange={onChange} />;
});

function App() {
  const [val1, setVal1] = useState('');
  const [val2, setVal2] = useState('');

  const onChange1 = useCallback( evt => {
    setVal1(evt.target.value);
  }, []);

  const onChange2 = useCallback( evt => {
    setVal2(evt.target.value);
  }, []);

  return (
  <>
    <Child val={val1} onChange={onChange1}/>
    <Child val={val2} onChange={onChange2}/>
  </>
  );
}

上面的例子中,如果不用useCallback, 任何一个输入框的变化都会导致另一个输入框重新渲染。代码在这里

五、总结

本文深入讲解了使用 hooks 过程中死循环产生的原因,并给出了解决方案。useCallback并不是提高性能的银弹,错误的使用反而会适得其反。

查看原文

认证与成就

  • 获得 41 次点赞
  • 获得 243 枚徽章 获得 3 枚金徽章, 获得 56 枚银徽章, 获得 184 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2016-09-02
个人主页被 2.1k 人浏览