看完了这本书之后,我更觉得《算法图解》是一本算法科普书。
如果你想学习算法,这本书是不适合的,如果你只想了解一下算法,这本书是不错的。
前面部分介绍了一些简单的算法知识,后面说了一些复杂的算法和有趣的问题,供读者自己去深入研究算法问题。
二分法查找
- 二分法查找是利用了有序数组的特点,通过比较元素的大小,减少查找的次数。
- 二分法查找的复杂度为 \( O(log_2 n) \)。
js实现:
1function binarySearch(arr, target) {2 let low = 0;3 let high = arr.length - 1;4
5 while (low <= high) {6 let mid = Math.floor((low + high) / 2);7 let guess = arr[mid];8
9 if (guess === target) {10 return mid; // 找到目标值,返回索引11 } else if (guess < target) {12 low = mid + 1; // 目标值在右侧13 } else {14 high = mid - 1; // 目标值在左侧15 }16 collapsed lines
16 }17
18 return -1; // 未找到目标值19}20
21// 示例22const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];23const targetValue = 6;24
25const result = binarySearch(sortedArray, targetValue);26
27if (result !== -1) {28 console.log(`目标值 ${targetValue} 在数组中的索引是: ${result}`);29} else {30 console.log(`未找到目标值 ${targetValue}`);31}
选择排序
1function selectionSort(arr) {2 const n = arr.length;3
4 for (let i = 0; i < n - 1; i++) {5 // 假设当前位置的元素是最小的6 let minIndex = i;7
8 // 在未排序部分找到最小元素的索引9 for (let j = i + 1; j < n; j++) {10 if (arr[j] < arr[minIndex]) {11 minIndex = j;12 }13 }14
15 // 将最小元素与当前位置交换12 collapsed lines
16 if (minIndex !== i) {17 [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];18 }19 }20
21 return arr;22}23
24// 示例用法25const unsortedArray = [64, 25, 12, 22, 11];26const sortedArray = selectionSort(unsortedArray.slice());27console.log(sortedArray); // 输出 [11, 12, 22, 25, 64]
快速排序
1function quickSort(arr) {2 if (arr.length <= 1) {3 return arr; // 数组已经有序4 }5
6 const pivot = arr[0]; // 选择第一个元素作为基准7 const left = [];8 const right = [];9
10 for (let i = 1; i < arr.length; i++) {11 if (arr[i] < pivot) {12 left.push(arr[i]);13 } else {14 right.push(arr[i]);15 }10 collapsed lines
16 }17
18 // 递归排序左右子数组,然后合并19 return quickSort(left).concat(pivot, quickSort(right));20}21
22// 示例用法23const unsortedArray = [64, 25, 12, 22, 11];24const sortedArray = quickSort(unsortedArray.slice());25console.log(sortedArray); // 输出 [11, 12, 22, 25, 64]
递归
1// 计算阶乘的递归函数2function factorial(n) {3 // 基本情况:当 n 为 0 或 1 时,阶乘为 14 if (n === 0 || n === 1) {5 return 1;6 } else {7 // 递归情况:n 的阶乘等于 n 乘以 (n-1) 的阶乘8 return n * factorial(n - 1);9 }10}11
12// 示例用法13const result = factorial(5);14console.log(result); // 输出 120
五种常见的时间复杂度
由快到慢排序:
- \(O(log_n)\)
- \(O(n)\)
- \(O(n*log_n)\)
- \(O(n^2)\)
- \(O(n!)\)
补充:
- \( log_2 n \)代表中多少个2相乘等于n。
问题:
- js中关于数组、栈、队列、散列表的实现
- 如果你对数据库或高级数据结构感兴趣,请研究如下数据结构:B树,红黑树,堆,伸展树。