1.认识算法

1.1 什么是算法

解决某个实际问题的过程和方法

1.2 为什么要学习算法

可以训练编程思维

1.3 时间复杂度

时间复杂度是用于衡量算法运行时间随着输入规模增长而变化的趋势的指标。它通过分析算法中基本操作的执行次数与输入规模 n 的关系，并用大 O 符号表示，忽略常数因子和低阶项，专注于最高阶的项。

1.3.1 核心概念：

1. 大 O 符号（O）：表示算法的最坏时间复杂度，即运行时间的上界。例如：
   • O(1)：常数时间复杂度，如数组索引访问。
   • O(n)：线性时间复杂度，如遍历数组。
   • O(n²)：平方时间复杂度，如双重循环。
   • O(log n)：对数时间复杂度，如二分查找。
   • O(n log n)：线性对数时间复杂度，如归并排序。
2. 其他符号：
   • Ω(Omega)：表示最好情况下的时间复杂度（下界）。
   • Θ(Theta)：表示平均时间复杂度（紧确界）。
3. 计算方法：
   1. 基本操作：确定算法中的基本操作（如循环、条件判断）。
   2. 执行次数：计算基本操作执行的次数与 n 的关系。
   3. 简化表达式：保留最高阶项，忽略常数和低阶项。例如，3*n² + 2*n + 1 简化为 O(n²)。

1.3.2 常见示例：

• 单层循环：时间复杂度为 O(n)。

  1 2	for i in range(n): print(i)

• 双重循环：时间复杂度为 O(n²)。

  1 2 3

  for i in range(n): for j in range(n): print(i, j)

• 对数循环：时间复杂度为 O(logn)。

  1 2 3

  i = 1 while i < n: i *= 2

2.排序算法

按照指定的规则（一般字典排序）将数据按照顺序排序

2.1 冒泡排序（Bubble Sort）

通过相邻元素的比较和交换，将最大元素逐步“冒泡”到数组末端。每一轮排序确定一个当前区间的最大值位置，直到所有元素有序。属于稳定排序算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public static void BubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;

    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换操作
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                swapped = true;
            }
        }
        // 本轮无交换则提前终止
        if (!swapped) break;
    }
}

🔍 关键解析

2.1.1 循环控制逻辑

• 外层循环 i < n - 1：需要 n-1 轮遍历，因为每轮确定一个最大值。
• 内层循环 j < n - 1 - i：每轮比较范围递减，已排序部分不再参与比较。

2.1.2 提前终止机制

• 当某轮未发生任何交换时，说明数组已完全有序，可提前结束排序。
• 此优化使 最佳时间复杂度降为 O(n)（如输入数组本就有序时）。

⚙️ 复杂度分析

2.2 选择排序（Selection Sort）

通过不断选择剩余元素中的最小值，依次放置到数组前部的有序区。核心思想是”选择最小，交换位置”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static void selectionSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 交换最小值到当前位置
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

🔍 关键解析

2.2.1 核心操作流程

• 步骤一：在未排序子数组中找到最小值。
• 步骤二：与当前有序区末尾元素交换。
• 步骤三：扩展有序区。

2.2.2 交换优化

• 每轮最多只交换一次（比冒泡排序交换次数少）。

⚙️ 复杂度分析

3.查找算法

3.1 二分查找（Binary Search）

二分查找是一种高效的有序数组查找算法，通过不断将搜索范围减半快速定位目标值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }

    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

🔍 关键解析

3.1 循环条件

• left <= right：确保覆盖闭区间所有元素（包括单个元素的边界情况）。

3.2 防溢出中间值计算

• 正确写法：mid = left + (right - left) / 2。

3.3 边界更新逻辑

• 严格排除已检查元素：
  • arr[mid] < target → left = mid + 1。
  • arr[mid] > target → right = mid - 1。

⚙️ 复杂度分析