Cirry's Blog

看完了这本书之后，我更觉得《算法图解》是一本算法科普书。

如果你想学习算法，这本书是不适合的，如果你只想了解一下算法，这本书是不错的。

前面部分介绍了一些简单的算法知识，后面说了一些复杂的算法和有趣的问题，供读者自己去深入研究算法问题。

二分法查找

二分法查找是利用了有序数组的特点，通过比较元素的大小，减少查找的次数。
二分法查找的复杂度为 \( O(log_2 n) \)。

js实现：

1
function 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
// 示例
22
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
23
const targetValue = 6;
24

25
const result = binarySearch(sortedArray, targetValue);
26

27
if (result !== -1) {
28
  console.log(`目标值 ${targetValue} 在数组中的索引是: ${result}`);
29
} else {
30
  console.log(`未找到目标值 ${targetValue}`);
31
}

选择排序

1
function 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
// 示例用法
25
const unsortedArray = [64, 25, 12, 22, 11];
26
const sortedArray = selectionSort(unsortedArray.slice());
27
console.log(sortedArray); // 输出 [11, 12, 22, 25, 64]

快速排序

1
function 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
// 示例用法
23
const unsortedArray = [64, 25, 12, 22, 11];
24
const sortedArray = quickSort(unsortedArray.slice());
25
console.log(sortedArray); // 输出 [11, 12, 22, 25, 64]

递归

1
// 计算阶乘的递归函数
2
function factorial(n) {
3
  // 基本情况：当 n 为 0 或 1 时，阶乘为 1
4
  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
// 示例用法
13
const result = factorial(5);
14
console.log(result); // 输出 120