学习 Web 和大前端

当前分类为 数据结构
作者 TONY 发布于 2018年08月07日

其中 f 是传入的比较函数,因此可进行自定义比较规则的排序。

const qsort = f => ([x, ...xn]) => x === undefined ? [] :
[...qsort(f)(xn.filter(a => f(a, x))), x,
...qsort(f)(xn.filter(a => !f(a, x)))]

这里主要是为了阐明思路,性能可以这样优化:

阅读全文
分类 数据结构
作者 TONY 发布于 2018年07月12日

不可变对象(Immutable object)就是创建之后不能被改变的对象,对 Immutable 对象的任何修改操作都会返回一个新的 Immutable 对象。

Persistent Data Structure

实现的原理是 Persistent Data Structure(持久化数据结构),也就是使用旧数据创建新数据时,要保证旧数据同时可用且不变。同时为了避免深拷贝把所有节点都复制一遍带来的性能损耗,Immutable 使用了结构共享,即如果对象树中一个节点发生变化,只修改这个节点和受它影响的父节点,其它节点则进行共享。

阅读全文
作者 TONY 发布于 2018年05月15日

每次递归进去都进行了数组的拷贝,因此还可以优化。然后还可以优化成迭代的。这里主要是阐明思路。

function merge(l, r) {
  var t = []

  while (l.length && r.length) 
    l[0] < r[0] ?
    t.push(l.shift()) : 
    t.push(r.shift())
  
  return [...t, ...l, ...r]
}

function mergeSort(a) {
  if (a.length === 1) 
    return a

  var m = ~~(a.length / 2)
    , l = a.slice(0, m)
    , r = a.slice(m)

  return merge(mergeSort(l), mergeSort(r))
}
阅读全文
分类 数据结构
作者 TONY 发布于 2018年05月10日
function adjust(a, s, m) {
  for (var j = 2 * s; j <= m; j *= 2) {
    if (j < m && a[j] < a[j + 1]) j++
    if (a[s] < a[j]) [a[s], a[j]] = [a[j], a[s]]
    s = j
  }
}

function heapSort(a) {
  for (var i = ~~((a.length - 1) / 2); i >= 1; i--) 
    adjust(a, i, a.length - 1)
  for (i = a.length - 1; i > 1; i--) {
    [a[1], a[i]] = [a[i], a[1]]
    adjust(a, 1, i - 1)
  }
  return a
}

为了方便下标从 1 开始。

阅读全文
分类 数据结构