algorithms
algorithms copied to clipboard
barretlee
All algorithms writing with javascript in the book 'Algorithms Fourth Edition'.
如果你是算法初学者，强烈推荐这个「算法可视化」工具（http://jasonpark.me/AlgorithmVisualizer/ ），很清晰地绘制了每一个基础算法的原理和运作流程。 仓库地址：https://github.com/parkjs814/AlgorithmVisualizer
#25 中提到的顺序查找，是通过 key 遍历查找链表拿到对应的 value，其插入动作也是一个查询的过程——找到了 key 就重置 value，否则在链表最前方插入节点。构建这种无序的链表，成本很低，但由于其数据结构的熵比较大，做大量操作时成本偏高，尤其是链表很长的时候。 二分查找（Binary Search），就需要我们在构建符号表的时候将数据结构规范化。通过一个数组来储存数据的 keys，然后在对应的另一个数组中储存 vals，通过下表将 key 和 val 意义对应起来。 而在构建符号表的时候，可以通过二分法就行处理，如： [/chapters/chapter-3-searching/3.1-elementary-symbol-tables/binarySearchST.js](https://github.com/barretlee/algorithms/blob/master/chapters/chapter-3-searching/3.1-elementary-symbol-tables/binarySearchST.js) ```js function binarylSearchST() { var keys = [], vals = []; return...
顺序查找（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,...
插入排序和选择排序是两种最基本的排序算法，思路完全不一样，但是细思一番，还是挺有意思的： - `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; }...
动态联通性这块的算法还是有点不好理解，下面是效率递增的三个算法： - [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++) {...