L6 - 算法优化与多维数组

📚 核心知识模块

🔥 重点升级内容

1. 排序算法深度对比

冒泡排序模板

1
2
3
4
5
6
7
8
9
10
11
12
void bubbleSort(int arr[], int n) {
    for(int i=0; i<n-1; i++) {
        bool swapped = false; // 优化标记
        for(int j=0; j<n-1-i; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if(!swapped) break; // 提前终止
    }
}

计数排序模板

1
2
3
4
5
6
7
8
9
10
11
12
13
void countingSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr+n);
    int* count = new int[maxVal+1]{0};
    
    for(int i=0; i<n; i++) count[arr[i]]++;
    
    int index = 0;
    for(int i=0; i<=maxVal; i++) {
        while(count[i]--) arr[index++] = i;
    }
    
    delete[] count;
}

算法对比表

算法 时间复杂度 空间复杂度 适用场景
冒泡排序 O(n²) O(1) 教学演示、小数据集
计数排序 O(n+k) O(k) 整数范围较小的情况
STL sort O(n log n) O(log n) 通用场景

2. STL函数实战

内置函数应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <algorithm>
#include <cmath>

// 1. 快速排序
sort(arr, arr+n); // 默认升序
sort(arr, arr+n, greater<int>()); // 降序

// 2. 数值交换
swap(a, b);

// 3. 数学函数
pow(2, 3); // 8
sqrt(16);  // 4
abs(-5);   // 5

3. 多维数组进阶

动态二维数组

1
2
3
4
5
6
7
8
9
10
11
// 创建
int** matrix = new int*[rows];
for(int i=0; i<rows; i++) {
    matrix[i] = new int[cols];
}

// 释放
for(int i=0; i<rows; i++) {
    delete[] matrix[i];
}
delete[] matrix;

矩阵转置算法

1
2
3
4
5
6
7
void transpose(int** mat, int n) {
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            swap(mat[i][j], mat[j][i]);
        }
    }
}

🚀 新增训练体系

案例1：排序算法性能分析器

1
2
3
4
5
6
7
8
9
10
11
12
13
void testSort(void (*sortFunc)(int[], int), int arr[], int n) {
    auto start = chrono::high_resolution_clock::now();
    sortFunc(arr, n);
    auto end = chrono::high_resolution_clock::now();
    cout << "耗时: " 
         << chrono::duration_cast<microseconds>(end-start).count()
         << "μs" << endl;
}

// 使用示例
int arr1[] = {/*...*/}, arr2[] = {/*...*/};
testSort(bubbleSort, arr1, 1000);
testSort(countingSort, arr2, 1000);

案例2：成绩管理系统（二维数组版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int SUBJECTS = 3; // 语文、数学、英语

// 输入学生成绩
void inputScores(int** scores, int students) {
    for(int i=0; i<students; i++) {
        for(int j=0; j<SUBJECTS; j++) {
            cin >> scores[i][j];
        }
    }
}

// 计算学科平均分
void calcAverage(int** scores, int students) {
    for(int j=0; j<SUBJECTS; j++) {
        double sum = 0;
        for(int i=0; i<students; i++) {
            sum += scores[i][j];
        }
        cout << "学科" << j+1 << "平均分: " 
             << fixed << setprecision(1) << sum/students << endl;
    }
}