Barret李靖

顺序查找（Sequential Search），需要通过链表构建一张深度为 N 的无序符号表。你可以简单地理解它为一个数组，只不过它的每个单元都是一个键值对，并且它的数据结构比数组更加松散，便于我们做插入/删除等操作。 无序符号表的实现，十分简单，可以看这里： [chapters/chapter-3-searching/3.1-elementary-symbol-tables/sequentialSearchST.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-3-searching/3.1-elementary-symbol-tables/sequentialSearchST.js) ```js function sequentialSearchST() { function Node(key, val, next) { this.key = key; this.val = val; this.next = next; } var first = null; return...

排序这块我们已经讨论很多了（ #6 #8 #9 #10 )，从最开始基本的冒泡、插入、选择和希尔排序，到分治思想的延伸——归并排序（自顶向下和自底向上），再到归并排序的互补算法——快排，然后学习了新的数据结构——二叉堆，于是有了堆排序。 二叉堆是一种数据结构，他的每一个二叉树点元素数值都会比下面两个节点元素的数值要大，因为这种数据接口包含的信息量很大，而得到这种数据结构的成本是很低的，构建一个二叉堆的算法并不复杂： [/chapters/chapter-2-sorting/2.4-priority-queues/priorityQueueAdd.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-2-sorting/2.4-priority-queues/priorityQueueAdd.js) ``` javascript function priorityQueueAdd(input) { var output = []; output[1] = input[0]; for(var i = 1, len = input.length; i < len;...

#10 中提到了快排和快排的改进算法。当待排序的数据中存在大量重复元素时，快排的效率会不太高，当遇到重复元素的时候，比较和交换都是赘余的，重复元素越多，性能越差，为了解决这个问题，我们引入了第三个变量，来标识重复元素区间，如下图所示： ``` +---------------------------------+ | v | +---------------------------------+ ↑ ↑ ↑ lt i gt ``` 大致的原理是：每次排序分组的时候，就会过滤掉重复元素，这样，进入递归的元素就少了很多，因此而提高效率。 [/chapters/chapter-2-sorting/2.3-quicksort/quick3way.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-2-sorting/2.3-quicksort/quick3way.js) ``` javascript function quick3way(input) { sort(0, input.length - 1); return input; function sort(start,...

Three basic Sort Algorithms

1

插入排序和选择排序是两种最基本的排序算法，思路完全不一样，但是细思一番，还是挺有意思的： - `insertion sort`，[插入排序](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-2-sorting/2.1-elementary-sorts/insertion.js)，思路简单来说就是把自己插入到已排好序的列表中去，交换也是颇为频繁的。 ``` javascript function insertion(input) { for(var i = 1, len = input.length; i < len; i++) { for(var j = i; j > 0; j--) {...

#6 和 #8 讨论了数据的基本排序方法，#9 利用间隔处理的方式，减少数据之间的对比和交换。#9 中讨论了归并排序，将一个数组拆分成两个，然后合并处理，进而有了递归归并的思考。 而本节提出了一种更加高效的排序方法，这种算法跟归并排序是互补的，归并排序大致思路是`分-排序合`，而本节提出的快排采用的思路是`排序分-合`，把排序这种损耗比较大的操作前置了，所以效率更高。 [/chapters/chapter-2-sorting/2.3-quicksort/quicksort.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-2-sorting/2.3-quicksort/quicksort.js) ``` javascript function quicksort(input) { sort(0, input.length - 1); return input; function sort(start, end) { if(start >= end) { return; } var...

#6 和 #8 是都是从头到尾去遍历数据，不可避免的带来很多交换操作。归并排序是一种用空间换时间的排序算法，一个数组截断成两个子数组，子数据排好序后合并到一起。 [/chapters/chapter-2-sorting/2.2-mergesort/merge.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-2-sorting/2.2-mergesort/merge.js) ``` javascript function merge(input1, input2) { var i = 0, j = 0; var output = []; while(i < input1.length || j < input2.length) {...

#6 提到了三种最基本的排序算法，这里要提到的希尔排序，有点不好理解。 [/chapters/chapter-2-sorting/2.1-elementary-sorts/shell.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-2-sorting/2.1-elementary-sorts/shell.js) ``` javascript function shell(input) { var h = 1; var len = input.length; while(h < Math.floor(len / 3)) { h = h * 3 + 1; }...

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

1

动态联通性这块的算法还是有点不好理解，下面是效率递增的三个算法： - [unionFind.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.5-case-study-union-find/unionFind.js) - [quickUnion.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.5-case-study-union-find/quickUnion.js) - [weightedQuickUnion.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.5-case-study-union-find/weightedQuickUnion.js) 回到家再继续分析这几个算法；） ``` javascript function weightedQuickUnion(input, combo) { var sz = []; for(var i = 0, len = input.length; i < len; i++) {...

> 从一堆顺序排列的整数中任选三个，其和为 0 则为一组，类似这样的组有多少？ 分析方法：任选两个组合为 0，得出一个暴力算法：[twoSum.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.4-analysis-of-algorithms/twoSum.js)，类比可以得到 [threeSum.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.4-analysis-of-algorithms/threeSum.js) 两个算法的时间复杂度都是很高的，结合 #1 提到的二分法降低复杂度，得到：[twoSumFast.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.4-analysis-of-algorithms/twoSumFast.js) 和 [threeSumFast.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.4-analysis-of-algorithms/threeSumFast.js)。 代码地址：[/chapters/chapter-1-fundamentals/1.4-analysis-of-algorithms/threeSumFast.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.4-analysis-of-algorithms/threeSumFast.js) ``` javascript function threeSumFast(input) { var counter = 0; for(var i = 0, len = input.length; i...

Dijkstra double stack

1

[/chapters/chapter-1-fundamentals/1.3-bags-queues-ans-stacks/evaluate.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-1-fundamentals/1.3-bags-queues-ans-stacks/evaluate.js) 双栈算法表达式求值算法，例如 `( 1 + ( ( 2 + 3 ) * ( 4 + 5 ) )`