算法与数据结构核心学习笔记

一、时间复杂度分析

1. 对数型嵌套循环

count = 0;
for(k=1 ; k <= n ;k*=2){
    for(j=1 ; j<n ; j++){
        操作
    }
}

详细分析：

外层循环：变量 k 从 1 开始，每次乘以 2，直到超过 n。执行次数为 log₂n 次。
内层循环：变量 j 从 1 递增到 n-1，每次执行固定 n-1 次，与外层 k 无关。
总执行次数：log₂n × (n-1) ≈ n log n。
结论：时间复杂度为 O(n log n)。

2. 双层嵌套循环

def fun(lists):
    sum = 0
    for i in range(len(lists)):
        tmp = lists[i]
        for j in range(len(lists)):
            sum += tmp
    return sum

print(fun(数组))

详细分析：

外层循环：遍历整个数组，执行 len(lists) 次，记为 n。
内层循环：对于外层的每一次迭代，内层都完整遍历一次数组，执行 n 次。
总执行次数：n × n = n²。
结论：时间复杂度为 O(n²)。

3. 递归函数

void foo(int n, int x, int y){
    int z = 0;
    if(n <= 0){
        z = x + y;
    }else{
        foo(n-1, x+1, y);
        foo(n-1, x, y+1);
    }
}

详细分析：

递归结构：每次调用产生 2 个新的递归调用，递归深度为 n。
调用树形态：这是一棵满二叉树。
节点总数计算：第 0 层 1 个，第 1 层 2 个，…，第 n 层 2ⁿ 个。

Total = 2⁰ + 2¹ + 2² + … + 2ⁿ = 2^(n+1) - 1
结论：时间复杂度为 O(2ⁿ)。

4. 分析方法总结

场景	分析策略	关键点
递归	递归调用树分析	计算总调用次数或递归深度与分支数的关系
嵌套循环	乘积法则	总次数 = 外层次数 × 内层次数
内层执行次数和	累加求和	若内层次数随外层变化，需计算 Σ
单层循环	直接计数	关注循环变量的变化步长

二、十大排序算法详解

1. 冒泡排序

核心思想：重复遍历数组，比较相邻元素，若顺序错误则交换，使较大元素逐步"冒泡"到末尾。
时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

2. 选择排序

核心思想：将数组分为已排序和未排序两部分，每次从未排序部分选择极值（最小/最大），追加到已排序部分末尾。
时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定（交换操作可能改变相同元素的相对位置）

3. 插入排序

核心思想：将数组分为已排序和未排序两部分，从未排序部分取值，在已排序部分找到正确位置并插入。
时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

4. 希尔排序

核心思想：插入排序的改进版（缩小增量排序）。设定间隔 gap 将数组分组，对每组进行插入排序，逐步缩小 gap，最后 gap=1 时完成整体排序。
时间复杂度：O(n log n) ~ O(n²)（取决于间隔序列的选择）
空间复杂度：O(1)
稳定性：不稳定

5. 计数排序

核心思想：非比较排序。统计每个元素出现的次数，根据计数结果重建有序数组。
时间复杂度：O(n + k)，k 为数据范围
空间复杂度：O(k)
稳定性：稳定
适用场景：数据范围较小的整数排序

6. 基数排序

核心思想：非比较排序。按位（个位、十位、百位…）依次对数据进行排序，通常结合计数排序实现。
时间复杂度：O(n × k)，k 为数字位数
空间复杂度：O(n + k)
稳定性：稳定
适用场景：固定位数的整数排序

7. 归并排序

核心思想：分治法。将数组递归地分成两半分别排序，然后合并两个有序子数组。
时间复杂度：O(n log n)
空间复杂度：O(n)（需要辅助数组）
稳定性：稳定

Java 完整实现

package cn.wolfcode;

import java.util.Arrays;

public class GuiBingSorted {
    public static void merge(int[] arr, int left, int mid, int right, int[] temp){
        int i = 0;
        int j = left; 
        int k = mid + 1;
        
        // 比较左右两部分，按序放入临时数组
        while(j <= mid && k <= right){
            if (arr[j] < arr[k]){
                temp[i++] = arr[j++];
            }else {
                temp[i++] = arr[k++];
            }
        }
        
        // 左侧有剩余，直接追加
        while (j <= mid){
            temp[i++] = arr[j++];
        }
        
        // 右侧有剩余，直接追加
        while (k <= right){
            temp[i++] = arr[k++];
        }
        
        // 将临时数组数据写回源数组
        for (int t = 0; t < i; t++) {
            arr[left + t] = temp[t];
        }
    }

    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        if (left < right){
            int mid = (left + right) / 2;
            // 左侧归并
            mergeSort(arr, left, mid, temp);
            // 右侧归并
            mergeSort(arr, mid + 1, right, temp);
            // 合并
            merge(arr, left, mid, right, temp);
        }
    }

    public static void main(String[] args) {
        int[] arr = {28, 12, 19, 50, 93, 66, 60, 58, 54, 79};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }
}

8. 堆排序

核心思想：利用二叉堆（大顶堆/小顶堆）数据结构。将数组构造成堆，反复取出堆顶元素（最大/最小）并重建堆。
时间复杂度：O(n log n)
空间复杂度：O(1)
稳定性：不稳定

9. 快速排序

核心思想：分治法。选择一个基准元素（pivot），将数组分为小于基准和大于基准的两部分，递归排序。
时间复杂度：平均 O(n log n)，最坏 O(n²)
空间复杂度：O(log n)（递归栈空间）
稳定性：不稳定

Java 完整实现

package cn.wolfcode;

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int[] arr, int left, int right) {
        int i, j, temp, t;
        if (left > right){
            return;
        }
        
        i = left;
        j = right;
        // 基准点
        temp = arr[left];
        
        while (i < j){
            // 先推动右侧指针向左侧移动，找小于基准的
            while (temp <= arr[j] && i < j){
                j--;
            }
            // 推动左侧指针向右侧移动，找大于基准的
            while (temp >= arr[i] && i < j){
                i++;
            }
            // 如果两个指针没有重合，交换
            if(i < j){
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        
        // 双指针重合，将基准值放到正确位置
        arr[left] = arr[i];
        arr[i] = temp;
        
        // 左侧快排
        quickSort(arr, left, i - 1);
        // 右侧快排
        quickSort(arr, i + 1, right);
    }

    public static void main(String[] args) {
        int[] arr = {28, 12, 19, 50, 93, 66, 60, 58, 54, 79};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

10. 桶排序

核心思想：将数组元素分配到有限数量的"桶"中，每个桶再单独排序（可用其他排序算法），最后按顺序收集桶中元素。
时间复杂度：O(n + k)，k 为桶的数量
空间复杂度：O(n + k)
稳定性：稳定
适用场景：数据均匀分布的浮点数或整数

三、十大排序算法对比总结

排序算法	时间复杂度 (最好/平均/最坏)	空间复杂度	稳定性	排序方式
冒泡排序	O(n) / O(n²) / O(n²)	O(1)	稳定	比较
选择排序	O(n²) / O(n²) / O(n²)	O(1)	不稳定	比较
插入排序	O(n) / O(n²) / O(n²)	O(1)	稳定	比较
希尔排序	O(n log n) / O(n^1.3) / O(n²)	O(1)	不稳定	比较
归并排序	O(n log n) / O(n log n) / O(n log n)	O(n)	稳定	比较
快速排序	O(n log n) / O(n log n) / O(n²)	O(log n)	不稳定	比较
堆排序	O(n log n) / O(n log n) / O(n log n)	O(1)	不稳定	比较
计数排序	O(n+k) / O(n+k) / O(n+k)	O(k)	稳定	非比较
桶排序	O(n+k) / O(n+k) / O(n²)	O(n+k)	稳定	非比较
基数排序	O(n·k) / O(n·k) / O(n·k)	O(n+k)	稳定	非比较

四、时间复杂度速查表

复杂度量级	名称	典型算法/场景
O(1)	常数阶	哈希表查找、数组下标访问、简单赋值
O(log n)	对数阶	二分查找、平衡二叉搜索树操作
O(n)	线性阶	线性扫描、计数排序、桶排序
O(n log n)	线性对数阶	归并排序、快速排序（平均）、堆排序
O(n²)	平方阶	冒泡排序、选择排序、插入排序、双层嵌套循环
O(n³)	立方阶	Floyd-Warshall 算法、三层嵌套循环
O(2ⁿ)	指数阶	暴力递归（如斐波那契递归）、子集枚举
O(n!)	阶乘阶	旅行商问题（TSP）暴力解、全排列生成