一、开场：算法世界的奇妙之旅

标题：解锁算法密码 - 探索排序与查找的奥秘

副标题：用算法思维解决实际问题

引入方式：展示一个杂乱的书架和一个整理有序的书架，提问学生如果要在书架上找一本书，在哪个书架上更容易找到。由此引出排序和查找算法在生活中的直观体现，进而导入课程，让学生明白算法可以帮助我们更高效地处理各种实际问题。

配图：选择一张对比杂乱书架和整齐书架的图片，或者用简单的流程图展示从无序到有序以及查找过程的图片，让学生对算法的作用有初步认识。

二、排序算法初体验

排序算法的概念

讲解排序算法是将一组数据按照特定的顺序（如升序或降序）进行排列的方法。排序在日常生活和计算机科学中都有广泛应用，比如成绩排名、文件按日期排序等。

举例说明排序的重要性，以电商平台的商品价格排序为例，方便用户快速找到价格合适的商品。

冒泡排序算法

原理讲解：通过多次比较相邻的元素，如果顺序错误就交换它们，每一轮比较都会将最大（或最小）的元素 “冒泡” 到数组的末尾（或开头）。以从小到大排序为例，展示如何依次比较相邻元素并交换，如对数组[5, 3, 4, 1, 2]进行冒泡排序，第一轮比较后数组变为[3, 4, 1, 2, 5]，经过多轮比较最终得到有序数组[1, 2, 3, 4, 5]。

代码示例：

#include <iostream>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 3, 4, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << "排序前的数组: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    bubbleSort(arr, n);

    std::cout << "排序后的数组: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码分析：外层循环控制排序的轮数，内层循环用于每一轮比较相邻元素并交换。if (arr[j] > arr[j + 1])判断相邻元素大小，若顺序错误则交换，通过temp临时变量实现交换。

选择排序算法

原理讲解：每一轮从未排序的元素中选择最小（或最大）的元素，将其与未排序部分的第一个元素交换位置，逐步将数组变为有序。例如对数组[5, 3, 4, 1, 2]进行选择排序，第一轮选择最小的元素 1，与第一个元素 5 交换，数组变为[1, 3, 4, 5, 2]，经过多轮选择和交换得到有序数组[1, 2, 3, 4, 5]。

代码示例：

#include <iostream>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex!= i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    int arr[] = {5, 3, 4, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    std::cout << "排序前的数组: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    selectionSort(arr, n);

    std::cout << "排序后的数组: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码分析：外层循环控制选择的轮数，内层循环用于找到未排序部分的最小元素的索引minIndex。若minIndex不等于当前索引i，则交换这两个位置的元素。

三、查找算法大揭秘

查找算法的概念

讲解查找算法是在一组数据中寻找特定元素的方法。查找在数据库查询、文件搜索等场景中至关重要，比如在学生成绩表中查找某个学生的成绩。

举例说明查找的实际应用，如在图书馆系统中查找某本书的位置。

顺序查找算法

原理讲解：从数组的第一个元素开始，依次与要查找的目标元素进行比较，直到找到目标元素或遍历完整个数组。例如在数组[3, 7, 1, 9, 4]中查找元素 7，从第一个元素 3 开始比较，直到找到元素 7。

代码示例：

#include <iostream>

int sequentialSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {3, 7, 1, 9, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int result = sequentialSearch(arr, n, target);
    if (result!= -1) {
        std::cout << "目标元素 " << target << " 在数组中的索引是: " << result << std::endl;
    } else {
        std::cout << "目标元素 " << target << " 不在数组中" << std::endl;
    }

    return 0;
}

代码分析：通过for循环遍历数组，使用if (arr[i] == target)判断当前元素是否为目标元素，若是则返回其索引，遍历结束未找到则返回 - 1。

二分查找算法（针对有序数组）

原理讲解：前提是数组已经有序，每次将数组中间的元素与目标元素比较，如果相等则找到；如果目标元素小于中间元素，则在数组的前半部分继续查找；如果目标元素大于中间元素，则在数组的后半部分继续查找，不断缩小查找范围，直到找到目标元素或确定目标元素不存在。例如在有序数组[1, 3, 5, 7, 9]中查找元素 5，首先比较中间元素 5 与目标元素 5，相等则找到。

代码示例：

#include <iostream>

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 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;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int result = binarySearch(arr, n, target);
    if (result!= -1) {
        std::cout << "目标元素 " << target << " 在数组中的索引是: " << result << std::endl;
    } else {
        std::cout << "目标元素 " << target << " 不在数组中" << std::endl;
    }

    return 0;
}

代码分析：使用while循环，通过left和right指针确定查找范围，计算中间索引mid。根据arr[mid]与target的比较结果，调整left或right指针，缩小查找范围。

四、算法应用实战

实际问题 1：学生成绩排序与查找

问题描述：假设有一个班级的学生成绩数组，要求先对成绩进行排序（升序），然后实现查找某个学生成绩的功能。

代码实现：

#include <iostream>

// 冒泡排序
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 顺序查找
int sequentialSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int scores[] = {85, 90, 78, 95, 88};
    int n = sizeof(scores) / sizeof(scores[0]);

    // 排序
    bubbleSort(scores, n);
    std::cout << "排序后的成绩: ";
    for (int i = 0; i < n; i++) {
        std::cout << scores[i] << " ";
    }
    std::cout << std::endl;

    // 查找
    int targetScore = 90;
    int result = sequentialSearch(scores, n, targetScore);
    if (result!= -1) {
        std::cout << "成绩 " << targetScore << " 在数组中的索引是: " << result << std::endl;
    } else {
        std::cout << "成绩 " << targetScore << " 不在数组中" << std::endl;
    }

    return 0;
}

分析与讲解：首先使用冒泡排序对成绩数组进行排序，然后使用顺序查找查找目标成绩。通过这个例子，让学生理解如何将排序和查找算法应用到实际问题中。

实际问题 2：电商商品价格查找与排序

问题描述：假设电商平台有一个商品价格数组，用户可以输入一个价格，查找该价格的商品是否存在，并且可以对商品价格进行排序（降序），方便用户查看价格从高到低的商品。

代码实现：

#include <iostream>

// 选择排序（降序）
void selectionSortDescending(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int maxIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j;
            }
        }
        if (maxIndex!= i) {
            int temp = arr[i];
            arr[i] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
    }
}

// 二分查找（针对有序数组，降序）
int binarySearchDescending(int arr[], int n, int target) {
    int left = 0, right = n - 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;
}

int main() {
    int prices[] = {100, 50, 150, 80, 120};
    int n = sizeof(prices) / sizeof(prices[0]);

    // 排序
    selectionSortDescending(prices, n);
    std::cout << "排序后的价格（降序）: ";
    for (int i = 0; i < n; i++) {
        std::cout << prices[i] << " ";
    }
    std::cout << std::endl;

    // 查找
    int targetPrice = 150;
    int result = binarySearchDescending(prices, n, targetPrice);
    if (result!= -1) {
        std::cout << "价格 " << targetPrice << " 在数组中的索引是: " << result << std::endl;
    } else {
        std::cout << "价格 " << targetPrice << " 不在数组中" << std::endl;
    }

    return 0;
}

分析与讲解：通过实现选择排序的降序版本和针对降序数组的二分查找，展示如何根据实际需求调整算法。让学生明白算法在不同场景下的灵活应用。

五、实践与巩固

练习题目

让学生编写一个程序，使用冒泡排序对一个整数数组进行降序排序，然后使用二分查找在排序后的数组中查找某个元素。要求添加注释说明代码功能。

给出一个包含排序和查找算法的程序，其中存在逻辑错误、边界条件处理不当等问题，让学生找出并改正，同时添加注释解释修改原因。

互动环节

开展小组竞赛，将学生分成小组共同完成练习题目。完成后，每个小组推选一名代表进行代码展示和讲解，其他小组进行提问和评价，教师进行总结和点评，获胜小组可获得小奖品，如编程书籍、在线课程优惠券等。

进行情景模拟编程，教师给出一些生活中需要排序和查找的场景，如运动会比赛成绩排名与查询、超市商品库存管理中的价格排序与商品查找等，让学生在规定时间内用所学算法编写代码实现，然后邀请学生上台分享自己的代码思路，增强学生的编程实践能力和表达能力。

六、回顾与总结

总结

回顾冒泡排序、选择排序、顺序查找和二分查找算法的原理、代码实现和特点。

总结算法在实际问题中的应用方法和技巧，强调根据具体问题选择合适算法的重要性。

对比不同排序和查找算法的时间复杂度和空间复杂度，帮助学生理解算法效率的概念。

拓展

鼓励学生课后尝试优化所学算法，如对冒泡排序进行优化，减少不必要的比较次数；或者尝试实现其他排序算法，如快速排序、归并排序等。

推荐一些算法学习资源，如在线算法学习平台（如 LeetCode、牛客网等）、算法书籍（如《算法导论》《数据结构与算法分析：C++ 描述》等），让学生在课后能进一步深入学习算法知识，提升算法设计和编程能力。

七、结束寄语

感谢语

感谢同学们在本节课的积极参与和认真学习，通过本节课的学习，大家对排序和查找算法有了深入的理解和掌握。希望大家在今后的编程学习中，能够灵活运用这些算法解决各种实际问题，不断提升自己的编程水平和算法思维能力。