导言 最近读了《数据结构与算法JavaScript描述》,除去书中一些代码错误之外,是一本让我有所收获的书。这里会说一些书中提及的算法及一点自己的理解,希望以后能熟练运用这些算法解决更复杂的问题。
排序算法 快速排序 快速排序是处理大数据集最快的排序算法之一。很多编程语言的排序函数都用到了快速排序,比如Chrome 的 JavaScript 引擎V8的Array.sort()
就使用快速排序和插入排序的结合。 快速排序的算法简单描述:
先确定一个“支点”(pivot)
将所有小于“支点”的值都放在该点的左侧,大于“支点”的值都放在该点的右侧
然后对左右两侧不断重复这个过程,直到所有排序完成。
如下图的例子: 用递归的思想可以这样实现,时间复杂度O(nlog2n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 function quickSort (arr ) { if (arr.length <= 1 ) { return arr } const pivot = Math .floor (arr.length / 2 ) const left = [] const right = [] for (let i = 0 , len = arr.length ; i < len; i++) { if (arr[i] < arr[pivot]) { left.push (arr[i]) } else if (arr[i] >= arr[pivot] && i !== pivot) { right.push (arr[i]) } } return quickSort (left).concat (arr[pivot], quickSort (right)) } const arr = [2 ,1 ,4 ,5 ,8 ,3 ]quickSort (arr, 0 , arr.length - 1 )
但是,这个实现的方法声明了一些数组,空间复杂度较大,内存占用较多。 下面是更好的原地排序的实现方法。 先看动图 具体实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 function partition (arr, left, right ) { const pivot = arr[left] let p = left for (let i = left + 1 ; i <= right; i++) { if (arr[i] < pivot) { swap (arr[++p], arr[i]) } } swap (pivot, arr[p]) return p } function quickSort (arr, left = 0 , right = arr.length - 1 ) { if (arr.length == 1 ) { return arr } if (left < right) { const p = partition (arr, left, right) quickSort (arr, left, p - 1 ) quickSort (arr, p + 1 , right) } } function swap (a, b) { let temp = b b = a a = temp }
检索算法 顺序查找 对于查找数据来说,顺序查找是最容易理解的方法,也属于暴力查找技巧的一种,适合于元素随机排列的数组。 具体实现如下,时间复杂度O(n)
1 2 3 4 5 6 7 8 function seqSearch (arr, data ) { for (let i = 0 , len = arr.length ; i < len; i++) { if (arr[i] === data) { return i } } return -1 }
因为在执行查找时可能会访问到数据结构里的所有元素,这种查找方法效率较低,尤其是数据量较大的情况下。 有一种优化的方法是使用自组织数据。这种策略具体是:通过将频繁查找到的元素置于数据集的起始位置来最小化查找次数。我们可以在程序运行过程中由程序自动组织数据,如下面的例子:
1 2 3 4 5 6 7 8 9 10 11 12 function seqSearch (arr, data ) { for (let i = 0 , len = arr.length ; i < len; i++) { if (arr[i] === data) { if (i > 0 ) { swap (arr[i], arr[i - 1 ]) return i - 1 } } } return -1 }
二分查找算法 而对于有序的数据,二分查找算法比顺序查找算法更高效。 二分查找算法简单描述:
将数组的第一个位置设置为下边界,最后一个元素设置为上边界
若下边界小于等于上边界则将中点(mid)设置为(上边界 + 下边界) / 2
如果mid小于查询值,则将下边界设置为 mid + 1,重复步骤2、3;如果mid大于查询值,则将上边界设置为mid - 1,重复步骤2、3;否则返回mid
具体实现如下,时间复杂度O(log2n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 function binSearch (arr, data ) { const upperBound = arr.length - 1 const lowerBound = 0 while (lowerBound <= upperBound) { const mid = Math .floor ((lowerCound + upperBound) / 2 ) if (data > arr[mid]) { lowerBound = mid + 1 } else if (data < arr[mid]) { upperBound = mid - 1 } else { return mid } } return -1 }
对于查找频繁的无序数据集,可以先进行一次快速排序然后实现二分查找算法。
数组去重 我们经常会遇到要对数组去重的情况。最容易理解的实现是遍历数组,进行顺序查找。具体实现如下,时间复杂度O(n^2)。
1 2 3 4 5 6 7 8 9 function unique (arr ) { let uqArr = [] for (let i = 0 , len = arr.length ; i < len; i++) { if (uqArr.indexOf (arr[i]) === -1 ) { uqArr.push (arr[i]) } } return uqArr }
时间复杂度更低的实现方式是利用散列表结构,但空间复杂度较高,用空间换时间。具体实现如下,时间复杂度O(n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 function uniqueHash (arr ) { let hash = {} let uqArr = [] let item for (let i = 0 , len = arr.length ; i < len; i++) { item = arr[i] if (!hash[item]) { hash[item] = true uqArr.push (item) } } return uqArr }
在上面的基础上,用开链法区分数据类型,解决如果数组的某元素是__proto__
和碰撞的问题。
1 2 3 4 5 6 7 8 9 10 11 12 13 function uniqueHash2 (arr ) { let hash = Object .create (null ) let uqArr = [] let item for (let i = 0 , len = arr.length ; i < len; i++) { item = arr[i] if (!hash[item][typeof item]) { hash[item][typeof item] = true uqArr.push (item) } } return uqArr }
高级算法 动态规划 我们可以通过与递归比较来理解动态规划:
递归:从顶部开始将问题分解,通过解决掉所有分解出小问题的方式,来解决整个问题
动态规划:从底部开始解决问题,将所有小问题解决掉,然后合并成一个整体解决方案,从而解决掉整个大问题
下面看一个简单的例子: 要实现斐波那契数列(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…)的计算,用递归的思想可以这样实现:
1 2 3 4 5 6 7 function recurFib (n ) { if (n < 2 ) { return n } else { return recurFib (n - 1 ) + recurFib (n - 2 ) } }
这是较容易理解的一种实现方式。但是,我们会发现,太多值在递归调用中被重新计算,当要计算的n较大时,执行效率很低。 这时,我们可以发现这个“大问题”是可以通过解决若干个“小问题”来解决的。而解决“小问题”有一个固定的公式,就是:Fib(n) = Fib(n - 1) + Fib(n - 2)
。从而想到,用动态规划来实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 function dynFib (n ) { if (n < 3 ) { const fib = n < 2 ? n : 1 return fib } else { const val = new Array (n + 1 ) val[1 ] = 1 val[2 ] = 1 for (let i = 3 ; i <= n; i++) { val[i] = val[i - 1 ] + val[i - 2 ] } return val[n] } }
这种实现方式用数组保存了中间结果,效率更高。 以后遇到能用递归解决的问题,如果有子问题结构,可以考虑尝试用动态规划解决。
贪心算法 贪心算法的策略是:总是会选择当下的最优解,而不去考虑这一次的选择会不会对未来的选择造成影响。通过做出一系列的局部“最优”选择,有可能带来最终的整体“最优”选择,也有可能是“次优”选择。 下面是商店找零的例子,最优解是令使用的硬币数最少。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 function makeChange (money ) { let coins = [] if (money % .25 < money) { coins[3 ] = parseInt (money / .25 ) money = money % .25 } if (money % .1 < money) { coins[2 ] = parseInt (money / .1 ) money = money % .1 } if (money % .05 < money) { coins[1 ] = parseInt (money / .05 ) money = money % .05 } coins[0 ] = parseInt (money / .01 ) console .log (coins[0 ] + '个1美分' ) console .log (coins[1 ] + '个5美分' ) console .log (coins[2 ] + '个10美分' ) console .log (coins[3 ] + '个25美分' ) }
在这种情况下,这种方案总是能找到最优解。但如果硬币的面额改为:.25, .6, .5, .3, .1。当遇到1时,按照贪心算法将分解为.6 + .3 + .1
,而最优解应该是.5 * 2
。 这里只举出几个简单的例子,关于动态规划和贪心算法还有更多的应用场景,这里不一一叙述了。
参考