轩枫阁

首页 / 搜索标签: 算法

深度剖析:如何实现一个 Virtual DOM 算法

看到一篇关于Virtual DOM的优秀文章,现转载

1 前言

本文会在教你怎么用 300~400 行代码实现一个基本的 Virtual DOM 算法,并且尝试尽量把 Virtual DOM 的算法思路阐述清楚。希望在阅读本文后,能让你深入理解 Virtual DOM 算法,给你现有前端的编程提供一些新的思考。

本文所实现的完整代码存放在 Github

2 对前端应用状态管理的思考

假如现在你需要写一个像下面一样的表格的应用程序,这个表格可以根据不同的字段进行升序或者降序的展示。 查看全文

2017/08 15  周二

常见排序以及其时间复杂度-面试必备收藏

选择排序

特点

不稳定,时间复杂度 O(n^2)

简介

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。

插入排序

特点

稳定,时间复杂度 O(n^2)

简介

插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤L[i],则L[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j]≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程,共需要(a),(b),(c)三次插入。

冒泡排序

特点

稳定,时间复杂度 O(n^2) 查看全文

2014/06 24  周二

程序员必知的十大基础实用算法及其讲解-面试必备收藏

算法一:快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

算法步骤:

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

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

Sorting_quicksort_anim

详细介绍:快速排序

算法二:堆排序算法

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

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤:

  1. 创建一个堆H[0..n-1]
  2. 把堆首(最大值)和堆尾互换
  3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
  4. 重复步骤2,直到堆的尺寸为1

查看全文

2014/06 24  周二

纸飞机许愿

x

钢琴节奏

请选择弹奏的曲谱

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 1
    • 2

    [返回曲谱列表]