barretlee/algorithms

All algorithms writing with javascript in the book 'Algorithms Fourth Edition'.

algorithms's Issues

BinarySearch

/chapter-1-fundamentals/1.1-programming-model/BinarySearch.js

Shell Sort

#6 提到了三种最基本的排序算法，这里要提到的希尔排序，有点不好理解。

/chapters/chapter-2-sorting/2.1-elementary-sorts/shell.js

function shell(input) {
  var h = 1;
  var len = input.length;
  while(h < Math.floor(len / 3)) {
    h = h * 3 + 1;
  }
  while(h >= 1) {
    for(var i = h; i < len; i++)  {
      for(var j = i; j >= h; j -= h) {
        if(input[j] < input[j - h]) {
          input[j] = [input[j - h], input[j - h] = input[j]][0];
        }
      }
    }
    h = Math.floor(h / 3);
  }
  return input;
}

算法复杂不代表需要很多的代码去实现，因为代码表达的是过程，通过循环等方式可以很迅速实现一个过程，而算法是处理问题的方法，把它表达清楚可能就得费不少唇舌，甚至还得配上一些图辅助阅读。

希尔排序，大概的思路就是不断地从整体上调整数据的顺序，将比较大的数据尽量往后挪，比较小的数据尽量往前挪。数据的搬移也不是一步完成，每一次搬移都会将数据分块，分块的目的是尽可能的搬移距离比较远的数据，从而减少比较操作和交换操作。

Three basic Sort Algorithms

插入排序和选择排序是两种最基本的排序算法，思路完全不一样，但是细思一番，还是挺有意思的：

• insertion sort，插入排序，思路简单来说就是把自己插入到已排好序的列表中去，交换也是颇为频繁的。

function insertion(input) {
  for(var i = 1, len = input.length; i < len; i++) {
    for(var j = i; j > 0; j--) {
      if(input[j] < input[j - 1]) {
        input[j] = [input[j - 1], input[j - 1] = input[j]][0];
      }
    }
  }
  return input;
}

• selection sort，选择排序，选择排序只对最后一个被选中的元素排序。它会往后找到包括自己在内最小的一个元素，替换自己。简单来说就是把第 i 小的元素放到第 i 个序位上。

function selection(input) {
  for(var i = 0, len = input.length; i < len - 1; i++) {
    var min = i;
    for(var j = i + 1; j < len; j++) {
      if(input[j] < input[min]) {
        min = j;
      }
    }
    input[i] = [input[min], input[min] = input[i]][0];
  }
  return input;
}

而冒泡排序，就更简单了，从第一个元素开始，往后比较，遇到比自己小的元素就交换位置，交换的次数最多，自然也是性能最差的。

function bubble(input) {
  for(var i = 0, len = input.length; i < len - 1; i++) {
    for(var j = i + 1; j < len; j++) {
      if(input[j] < input[i]) {
        input[j] = [input[i], input[i] = input[j]][0];
      }
    }
  }
  return input;
}

Thoughts（一些遐思）, update continuously

工作快两年时间了，这两年里我接触过很多系统和平台，也参与过不少系统和工程的建设，无论是编程能力还是沟通能力都有了质的飞跃。然而依然感觉缺了点什么。

技术和能力的成长有太多看得到的瓶颈，刚开始是因为缺乏知识和能力，看不到也摸不清一个领域的深度，这个时候如果不断地学习、不断地给大脑补给营养，两三年的时间会慢慢冲破这一层瓶颈。这个瓶颈期过了之后，再去学习新的知识提升就不明显了，如果你知道 log 函数曲线的走势，大概就能明白我的意思。所以第二个阶段重点不应该是狼吞虎咽地学习新技术，那些方法和经验会更加重要，参与到一些项目中，为项目的发展出谋划策，并不断在实践中留下沉淀和脚印，这样才能够在一个领域中走得更深、更远。

昨天跟 @wintercn 老湿促膝长谈，他给我了一些建议，我觉得挺有道理，不过还是觉得，学习依然是我的重心。过去两年更多的在提升自己的编程能力，在前端的知识边界上附近开荒，学的很浅薄。而今年需要沉下心来，把基本功打扎实。

所以你会慢慢发现，我今年的重心在对思维的训练上，主要分为两个方面，一是算法研究，二是系统性研究。算法的研究就跟机器学习一样，需要不断地做题、不断地挑战才能有突破，我相信这一块是熟能生巧，因为它很大部分都是硬知识，可以通过不断地学习来加深记忆，最近也在猛攻这些硬知识，希望在短时间内出点成效。而系统性的研究，还需要细细地琢磨，淘宝前端团队在工程和技术上领先国内绝大多数前端团队，领先可能不止半点丁点，按照 winter 的说法，差不多五年。所以问自己一个问题，假如有一个团队希望引入这些技术，我是否有能力 start from scratch？这里不仅仅是写代码的能力，还需要很强的工程能力和架构能力。

所以…努力吧！一切只是从零开始，后面的路还有很远。

Quick sort and improvement

#6 和 #8 讨论了数据的基本排序方法，#9 利用间隔处理的方式，减少数据之间的对比和交换。#9 中讨论了归并排序，将一个数组拆分成两个，然后合并处理，进而有了递归归并的思考。

而本节提出了一种更加高效的排序方法，这种算法跟归并排序是互补的，归并排序大致思路是分-排序合，而本节提出的快排采用的思路是排序分-合，把排序这种损耗比较大的操作前置了，所以效率更高。

/chapters/chapter-2-sorting/2.3-quicksort/quicksort.js

function quicksort(input) {
  sort(0, input.length - 1);
  return input;

  function sort(start, end) {
    if(start >= end) {
      return;
    }
    var mid = partition(start, end);
    sort(start, mid - 1);
    sort(mid + 1, end);
  }

  function partition(start, end) {
    var i = start, j = end + 1, k = input[start];
    while(true) {
      while(input[++i] < k) if( i === end) break;
      while(input[--j] > k) if( j === start) break;
      if(i >= j) break;
      input[i] = [input[j], input[j] = input[i]][0];
    }
    input[j] = [input[start], input[start] = input[j]][0];
    return j;
  }
}

这个算法写起来，感觉相当酸爽，因为这个排序思路太棒，情不自禁地热血沸腾。事实上，这个算法也是存在几个疑点的：

• 代码中的 mid 这个「哨兵」为啥要取第一个呢？
• partition 函数当 end - start 很小的时候效率还高么？

于是有了两个想法：

• 使用 input 的中位数作为「哨兵」
• 当 end - start 比较小的时候，大约为 5~15，改为其他比较高效的算法

今天只对第二个想法做了实践，基本改造如下：

chapters/chapter-2-sorting/2.3-quicksort/quicksortImprove.js

var delta = 5;
function quicksortImprove(input) {
  sort(0, input.length - 1);
  return input;

  // sort 和 partition 函数同上

  function insertion(start, end) {
    for(var i = start + 1, len = end - start; i < end; i++) {
      for(var j = i; j > start; j--) {
        if(input[j] < input[j - 1]) {
          input[j] = [input[j - 1], input[j - 1] = input[j]][0];
        }
      }
    }
  }
}

明天尝试下第一个想法，感觉这种探索还是十分有意思的！

Data Generator

数据生成器：./generator/index.js

提供了 7 个函数：

• getRandomNumber，生成一个随机数
• getRandomString，生成一个随机字符串
• getRandomNumbers，生成一个随机数组
• getDescRandomNumbers，同上，倒序
• getEscRandomNumbers，同上，顺序
• getRandomStrings，生成一串随机字符串
• noRepeat，字符串/数组去重

传参也具备鲁棒性，比如 getRandomNumbers：

• getRandomNumbers();
• getRandomNumbers(amount);
• getRandomNumbers(min, max);
• getRandomNumbers(amount, min, max);

默认长度为 20，随机数区间为 [0, 1E5]，随机字符串区间为 a-zA-Z0-9_。

后续会根据需要补充更多随机函数。

algorirhms

小胡子哥，算法这本书里的后续章节中的东西，大概什么时候可以弄好呢？

Binary Search

#25 中提到的顺序查找，是通过 key 遍历查找链表拿到对应的 value，其插入动作也是一个查询的过程——找到了 key 就重置 value，否则在链表最前方插入节点。构建这种无序的链表，成本很低，但由于其数据结构的熵比较大，做大量操作时成本偏高，尤其是链表很长的时候。

二分查找（Binary Search），就需要我们在构建符号表的时候将数据结构规范化。通过一个数组来储存数据的 keys，然后在对应的另一个数组中储存 vals，通过下表将 key 和 val 意义对应起来。

而在构建符号表的时候，可以通过二分法就行处理，如：

/chapters/chapter-3-searching/3.1-elementary-symbol-tables/binarySearchST.js

function binarylSearchST() {
  var keys = [], vals = [];
  return {
    keys: keys,
    vals: vals,
    put: function(key, val) {
      var pos = this.rank(key);
      var N = keys.length;
      if(pos == 0) {
        keys[0] = key;
        vals[0] = val;
      }
      if(pos < N && keys[pos] === key) {
        vals[pos] = val;
        return;
      }
      for(var i = N; i >= pos + 1; i--) {
        keys[i + 1] = keys[i];
        vals[i + 1] = vals[i];
      }
      keys[i] = key;
      vals[i] = val;
    },
    get: function(key) {
      var pos = this.rank(key);
      if(pos >= 0) {
        return {
          key: keys[pos],
          val: vals[pos]
        }
      }
      return -1;
    },
    rank: function(key) {
      var start = 0, end = Math.max(keys.length - 1, 0), mid;
      while(start < end) {
        mid = ((end - start) >> 1) + start;
        if(!keys[mid]) return mid;
        if(keys[mid] < key) end = mid - 1;
        else if (keys[mid] > key) start = mid + 1;
        return mid;
      }
      return start;
    }
  }
}

使用 rank 方法，让我们在构建和查询符号表的时候，效率都特别高。在一个长度为 N 的有序数组中进行二分查找最多需要 lgN + 1 次比较，然而插入效率却有点低，一次插入最坏的效果是需要 ~2N 次访问数组，也就是说构建一个长度为 N 的符号表需要 ~N² 次访问，效率比 #25 更低。

Quick sort improvement for which contains lots of duplicate data.

#10 中提到了快排和快排的改进算法。当待排序的数据中存在大量重复元素时，快排的效率会不太高，当遇到重复元素的时候，比较和交换都是赘余的，重复元素越多，性能越差，为了解决这个问题，我们引入了第三个变量，来标识重复元素区间，如下图所示：

+---------------------------------+
|  <v  |  =v  |=========|   > v   |
+---------------------------------+
       ↑      ↑         ↑
      lt      i         gt

大致的原理是：每次排序分组的时候，就会过滤掉重复元素，这样，进入递归的元素就少了很多，因此而提高效率。

/chapters/chapter-2-sorting/2.3-quicksort/quick3way.js

function quick3way(input) {
  sort(0, input.length - 1);
  return input;

  function sort(start, end) {
    if(start >= end) return;

    var lt = start, gt = end, i = start + 1, v = input[start];
    while(i <= gt) {
      if(input[i] < v) {
        input[lt] = [input[i], input[i] = input[lt]][0];
        lt++; i++;
      } else if(input[i] > v) {
        input[gt] = [input[i], input[i] = input[gt]][0];
        gt--;
      } else {
        i++;
      }
    }
    sort(start, lt - 1);
    sort(gt + 1, end);
  }
}

[每日一题] Two Sum

给定一个整数数组，其中有两项之和为一个特定的数字，假设每次 input 只有一个唯一解，不允许两次使用同一个元素，返回这两个数的索引。

比如：

给定 nums = [2, 7, 11, 15]，target = 9

由于 nums[0] + nums[1] = 9
所以返回 [0, 1]

Priority Queues, Heap Sort

排序这块我们已经讨论很多了（ #6 #8 #9 #10 )，从最开始基本的冒泡、插入、选择和希尔排序，到分治**的延伸——归并排序（自顶向下和自底向上），再到归并排序的互补算法——快排，然后学习了新的数据结构——二叉堆，于是有了堆排序。

二叉堆是一种数据结构，他的每一个二叉树点元素数值都会比下面两个节点元素的数值要大，因为这种数据接口包含的信息量很大，而得到这种数据结构的成本是很低的，构建一个二叉堆的算法并不复杂：

/chapters/chapter-2-sorting/2.4-priority-queues/priorityQueueAdd.js

function priorityQueueAdd(input) {
  var output = [];

  output[1] = input[0];
  for(var i = 1, len = input.length; i < len; i++) {
    output = swim(output, input[i]);
  }

  return output;

  function swim(arr, val) {
    arr.push(val);
    var k = arr.length - 1;
    while(k > 1 && arr[k >> 1] < arr[k]) {
      var p = k >> 1;
      arr[p] = [arr[k], arr[k] = arr[p]][0];
      k = p;
    }
    return arr;
  }
}

通过上浮的方式，不断插入新元素，既可形成一个二叉堆。这种优先队列最大的特点是，能够拿到很快拿到最大元素（顶部），当这个最大元素被删除（优先级最高的事务被处理完成）时，还能快速高效地将剩下的元素重整为一个二叉堆：

/chapters/chapter-2-sorting/2.4-priority-queues/priorityQueueDelete.js

function priorityQueueDelete(input) {
  var output = [];

  input.splice(1, 1);
  output = sink(input);

  return output;

  function sink(arr) {
    arr.splice(1, 0, arr.pop());
    var k = 1, N = arr.length - 1;
    while(2 * k <= N) {
      var j = 2 * k;
      if(j < N && arr[j] < arr[j + 1]) j++;
      if(arr[k] >= arr[j]) break;
      arr[k] = [arr[j], arr[j] = arr[k]][0];
      k = j;
    }
    return arr;
  }
}

一个二叉堆能够快速拿到最大元素，并且能够立即重新调整为二叉堆，基于这个特性，就有了堆排序：

/chapters/chapter-2-sorting/2.4-priority-queues/heapSort.js

function heapSort(input) {
  return sort(input);

  function sort (arr){
    var N = arr.length - 1;
    for(var k = N >> 2; k >= 1; k--) {
      arr = sink(arr, k, N);
    }
    while(N > 1) {
      arr[1] = [arr[N], arr[N] = arr[1]][0];
      N--;
      arr = sink(arr, 1, N);
    }
    return arr;
  }
  function sink(arr, k, N) {
    while(2 * k <= N) {
      var j = 2 * k;
      if(j < N && arr[j] < arr[j + 1]) j++;
      if(arr[k] >= arr[j]) break;
      arr[k] = [arr[j], arr[j] = arr[k]][0];
      k = j;
    }
    return arr;
  }
}

光看代码还是挺难理解的，脑海中必须有一个数组储存的堆模型。for 循环构造了堆（从 N/2 开始，跳过了所有大小为 1 的堆），注意，这里构造的并不是二叉堆，然后 while 循环将最大的元素 a[1] 和 a[n] 交换位置并修复堆，如此循环直到堆为空。

上面的排序用到的是 sink 方法，而 swim 方法也是可以用于排序算法之中的，这就是对应的下沉排序，感觉有点难理解。

Algorithms Visualizer

如果你是算法初学者，强烈推荐这个「算法可视化」工具（http://jasonpark.me/AlgorithmVisualizer/ ），很清晰地绘制了每一个基础算法的原理和运作流程。

仓库地址：https://github.com/parkjs814/AlgorithmVisualizer

Algorithms Analysis

从一堆顺序排列的整数中任选三个，其和为 0 则为一组，类似这样的组有多少？

分析方法：任选两个组合为 0，得出一个暴力算法：twoSum.js，类比可以得到 threeSum.js

两个算法的时间复杂度都是很高的，结合 #1 提到的二分法降低复杂度，得到：twoSumFast.js 和 threeSumFast.js。

代码地址：/chapters/chapter-1-fundamentals/1.4-analysis-of-algorithms/threeSumFast.js

function threeSumFast(input) {
  var counter = 0;
  for(var i = 0, len = input.length; i < len - 2; i++) {
    for(var j = i; j < len - 1; j++) {
      var searchKey = -1 * (input[i] + input[j]);
      if(rank(input, searchKey) > -1) {
        counter++;
      }
    }
  }
  return counter;

  function rank(a, k){
    var start = 0;
    var end = a.length - 1;
    while(start <= end) {
      var mid = Math.floor((end - start) / 2) + start;
      if(k < a[mid]) {
        end = mid - 1;
      } else if(k > a[mid]) {
        start = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  }
}

Sequential Search

顺序查找（Sequential Search），需要通过链表构建一张深度为 N 的无序符号表。你可以简单地理解它为一个数组，只不过它的每个单元都是一个键值对，并且它的数据结构比数组更加松散，便于我们做插入/删除等操作。

无序符号表的实现，十分简单，可以看这里：

chapters/chapter-3-searching/3.1-elementary-symbol-tables/sequentialSearchST.js

function sequentialSearchST() {

  function Node(key, val, next) {
    this.key = key;
    this.val = val;
    this.next = next;
  }

  var first = null;

  return {
    links: null,
    insertWhere: function(node, where) {
      var n = new Node(node.key, node.val);
      var l = this.links;
      if(where) {
        while(l) {
          if (l.key == where.key || l.val == where.val) {
            var ll = l.next;
            l.next = n;
            n.next = ll;
            break;
          }
          l = l.next;
        }
      } else {
        n.next = l;
        this.links = n;
      }
      return null;
    },
    findWhere: function(where) {
      var l = this.links;
      var depth = 0;
      while(l) {
        if(l.key == where.key || l.val == where.val) {
          var output = { depth: depth };
          for(var key  in l) if(key !== 'next') output[key] = l[key];
          return output;
        }
        depth++;
        l = l.next;
      }
      return -1;
    }
  }
}

一个长度为 N 的无序链表，每次查询和删除操作，最多需要 N 次，也就是说，我们构建一个长度为 N 的不重复无序链表，最多需要 ~N² / 2 次比较。

Dijkstra double stack

/chapters/chapter-1-fundamentals/1.3-bags-queues-ans-stacks/evaluate.js

双栈算法表达式求值算法，例如 ( 1 + ( ( 2 + 3 ) * ( 4 + 5 ) )

Merge Sort

#6 和 #8 是都是从头到尾去遍历数据，不可避免的带来很多交换操作。归并排序是一种用空间换时间的排序算法，一个数组截断成两个子数组，子数据排好序后合并到一起。

/chapters/chapter-2-sorting/2.2-mergesort/merge.js

function merge(input1, input2) {
  var i = 0, j = 0;
  var output = [];
  while(i < input1.length || j < input2.length) {
    if(i == input1.length) {
      output.push(input2[j++]);
      continue;
    }
    if(j == input2.length) {
      output.push(input1[i++]);
      continue;
    }
    if(input1[i] < input2[j]) {
      output.push(input1[i++]);
    } else {
      output.push(input2[j++]);
    }
  }
  return output;
}

上面是一个简单的合并算法，将两个有序数据合并为一个。有人应该会想到，既然一个数组可以打散成两个进行排序，那被打算的子数组是不是也可以继续被打散呢？

答案是肯定的。这是一种典型的分治**，递归归并。

/chapters/chapter-2-sorting/2.2-mergesort/mergeRecursiveTop2Bottom.js

function mergeRecursiveTop2Bottom(input) {

  return sort(input, 0, input.length - 1);

  function sort(arr, start, end) {
    if(start >= end) {
      return;
    }
    var mid = ((end - start) >> 1) + start;
    sort(arr, start, mid);
    sort(arr, mid + 1, end);
    return merge(arr, start, mid, end);
  }

  function merge(arr, start, mid, end) {
    var i = start, j = mid + 1, tmp = [];
    for(var k = start; k <= end; k++) {
      tmp[k] = arr[k];
    }
    for(k = start; k <= end; k++) {
      if(i > mid) {
        arr[k] = tmp[j++];
        continue;
      }
      if(j > end) {
        arr[k] = tmp[i++];
        continue;
      }
      if(tmp[i] < tmp[j]) {
        arr[k] = tmp[i++];
      } else {
        arr[k] = tmp[j++];
      }
    }
    return arr;
  }
}

上面的算法是自顶向下的递归归并，简单来说就是解决很多小问题，那么大问题也就自然而然的解决了；还有一种自底向上的归并，这种归并简单来说，就是把一个大问题分解为多个小问题，多个小问题的答案就能得出大问题的答案。从解决问题的方式来看，两种处理方式是互逆的。

/chapters/chapter-2-sorting/2.2-mergesort/mergeRecursiveTop2Bottom.js

function sort(arr) {
  for(var sz = 1, len = arr.length; sz < len; sz = sz * 2) {
    for(var start = 0; start < len - sz; start += sz * 2) {
      arr = merge(arr, start, start + sz - 1, Math.min(start + sz * 2 - 1, len - 1));
    }
  }
  return arr;
}
// merge 函数同上

不过自底向上的归并，在代码上稍微难理解一些，脑海重要有清晰的画卷，知道程序跑到哪一步了，尤其还需要处理边界问题。

union-find, quick-union, weighted-quick-union

动态联通性这块的算法还是有点不好理解，下面是效率递增的三个算法：

• unionFind.js
• quickUnion.js
• weightedQuickUnion.js

回到家再继续分析这几个算法；）

function weightedQuickUnion(input, combo) {
  var sz = [];
  for(var i = 0, len = input.length; i < len; i++) {
    sz.push(1);
  }
  for(var i = 0, len = combo.length; i < len; i++) {
    var p = combo[i][0];
    var q = combo[i][1];
    if(root(p) != root(q)) {
      if(sz[p] > sz[q]) {
        sz[p] += sz[q];
        input[q] = p;
      } else {
        sz[q] += sz[p];
        input[p] = q;
      }
    }
  }

  return input;

  function root(n) {
    while(input[n] != n) {
      n = input[n];
    }
    return n;
  }
}