当前位置：首页 > article >正文

快速排序＆Lambda表达式

article 2024/11/26 10:05:36

快速排序

912. 排序数组

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm> // 用于交换函数swap

using namespace std;

class Solution {
public:
    // 函数功能：对给定数组nums的指定区间[l, r]进行划分操作，用于快速排序
    // 参数说明：
    // nums：待排序的整数数组
    // l：区间左边界索引
    // r：区间右边界索引
    // 返回值：划分点的索引，使得划分点左边的元素都小于等于它，右边的元素都大于等于它
    int partition(vector<int>& nums, int l, int r) {
        // 选择区间的第一个元素nums[l]作为参照点（枢轴）
        int flag = nums[l];
        // 初始化指针i，从参照点的下一个位置开始，用于划分小于等于参照点的元素区域
        int i = l + 1;
        // 初始化指针j，从区间的右端点开始，用于划分大于等于参照点的元素区域
        int j = r;

        // 循环进行划分操作，直到i和j相遇
        while (true) {
            // 从左向右找第一个大于参照点的元素
            // 只要i还在有效区间内（i <= j）且当前元素nums[i]小于等于参照点，就继续向右移动i
            while (i <= j && nums[i] <= flag) {
                i++;
            }

            // 从右向左找第一个小于参照点的元素
            // 只要i还在有效区间内（i <= j）且当前元素nums[j]大于等于参照点，就继续向左移动j
            while (i <= j && nums[j] >= flag) {
                j--;
            }

            // 如果i大于j，说明已经完成了一次划分，此时小于等于参照点的元素都在左边，大于等于参照点的元素都在右边
            if (i > j) {
                break;
            }

            // 交换找到的两个元素，即把大于参照点的nums[i]和小于参照点的nums[j]进行交换
            // 这样可以使得左边的元素逐渐趋向于都小于等于参照点，右边的元素逐渐趋向于都大于等于参照点
            swap(nums[i], nums[j]);
            // 交换后，移动指针i和j，继续下一轮的查找和交换操作
            i++;
            j--;
        }

        // 将参照点放到正确的位置，即与j所指向的元素交换
        // 此时j所指向的位置就是参照点在排序后应该处于的位置，使得左边元素都小于等于它，右边元素都大于等于它
        swap(nums[l], nums[j]);

        // 返回划分点的索引
        return j;
    }

    // 函数功能：在给定数组nums的指定区间[l, r]内随机选择一个元素作为参照点，并进行划分操作
    // 参数说明：
    // nums：待排序的整数数组
    // l：区间左边界索引
    // r：区间右边界索引
    // 返回值：划分点的索引，使得划分点左边的元素都小于等于它，右边的元素都大于等于它
    int randomized_partition(vector<int>& nums, int l, r) {
        // 随机选一个位置和区间中的第一个位置交换，相当于随机选位
        // 生成一个在区间[l, r]内的随机索引i
        int i = rand() % (r - l + 1) + l;
        // 将随机选到的元素与区间的第一个元素nums[l]交换，使得第一个元素成为随机选取的参照点
        swap(nums[l], nums[i]);

        // 调用partition函数进行划分操作，并返回划分点的索引
        return partition(nums, l, r);
    }

    // 函数功能：对给定数组nums的指定区间[l, r]进行快速排序
    // 参数说明：
    // nums：待排序的整数数组
    // l：区间左边界索引
    // r：区间右边界索引
    // 无返回值，通过递归调用对数组进行排序，排序结果直接在原数组nums上体现
    void randomized_quicksort(vector<int>& nums, int l, int r) {
        // 如果区间左边界小于右边界，说明区间内至少有两个元素，需要进行排序
        if (l < r) {
            // 先进行随机划分操作，得到划分点的索引pos
            int pos = randomized_partition(nums, l, r);
            // 对划分点左边的子区间[l, pos - 1]进行快速排序
            randomized_quicksort(nums, l, pos - 1);
            // 对划分点右边的子区间[pos + 1, r]进行快速排序
            randomized_quicksort(nums, pos + 1, r);
        }
    }

    // 函数功能：对给定的整数数组nums进行排序，并返回排序后的数组
    // 参数说明：
    // nums：待排序的整数数组
    // 返回值：排序后的整数数组
    vector<int> sortArray(vector<int>& nums) {
        // 设置随机数生成器的种子，根据当前时间生成随机数序列
        // 这样每次运行程序时，随机选取参照点的操作都会有不同的结果，避免排序算法陷入最坏情况
        srand((unsigned)time(NULL));

        // 调用randomized_quicksort函数对整个数组进行快速排序，区间为[0, nums.size() - 1]
        randomized_quicksort(nums, 0, nums.size() - 1);

        // 返回排序后的数组
        return nums;
    }
};

什么是 C++ 中的 Lambda 表达式？它的作用是什么？

定义：
- Lambda 表达式是 C++11 引入的一种匿名函数。它可以在需要函数对象（如函数指针、std::function对象等）的地方定义和使用一个临时的函数。Lambda 表达式的语法形式如下：

[capture - list](parameters) mutable(optional) exception - specification(optional) -> return - type(optional) {
    function - body
}

其中，[capture - list]是捕获列表，用于指定在 Lambda 函数体中可以访问的外部变量；(parameters)是参数列表，和普通函数的参数列表类似，用于接收传入的参数；mutable关键字是可选的，用于修改按值捕获的变量（如果没有mutable，按值捕获的变量在 Lambda 函数体内是不可修改的）；exception - specification是可选的异常规范；-> return - type是可选的返回类型指定部分；function - body是函数体，包含了 Lambda 表达式要执行的具体代码。

作用：
- 作为回调函数使用：在很多 C++ 标准库算法（如std::for_each、std::transform等）中，需要提供一个函数对象来定义对容器元素的操作。Lambda 表达式可以方便地在调用这些算法的地方直接定义操作函数，而不需要单独定义一个函数或者函数对象类。例如：

#include <iostream>
#include <vector>
#include <algorithm>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::for_each(numbers.begin(), numbers.end(), [](int n) {
        std::cout << n * n << " ";
    });
    return 0;
}

在这个例子中，std::for_each算法遍历numbers向量中的每个元素，并对每个元素执行 Lambda 表达式定义的操作（这里是输出元素的平方）。
局部函数定义：当需要在一个函数内部定义一个临时使用的函数，并且这个函数的定义比较简单，不需要在多个地方复用的时候，Lambda 表达式可以提供简洁的定义方式。例如，在一个函数中，需要根据不同的条件计算不同的表达式，使用 Lambda 表达式可以避免定义多个小的辅助函数。
封装代码逻辑：可以将一些简单的逻辑封装在 Lambda 表达式中，提高代码的可读性和可维护性。例如，在排序操作中，可以使用 Lambda 表达式来定义比较规则。

Lambda 表达式可以捕获哪些类型的变量？有哪些捕获方式？

捕获类型：
- 值捕获：可以捕获外部变量的值。例如，int x = 10; auto lambda = [x]{ std::cout << x << std::endl; };，这里的lambda捕获了x的值。在 Lambda 函数体中使用的是x被捕获时的值。
- 引用捕获：可以捕获外部变量的引用。例如，int y = 20; auto lambda = [&y]{ y++; std::cout << y << std::endl; };，这里的lambda捕获了y的引用，在 Lambda 函数体中可以修改y的值。
捕获方式：
- 空捕获列表[]：表示不捕获任何外部变量，此时 Lambda 表达式内部不能访问外部变量。例如，auto lambda = []{ std::cout << "No external variables captured." << std::endl; };。
- 值捕获[x]或[x, y, z]等：按值捕获指定的外部变量。这些变量的值在 Lambda 表达式定义时被复制到 Lambda 函数内部，在 Lambda 函数内部对这些变量的修改不会影响外部的原始变量（除非使用mutable关键字）。例如，int a = 3; int b = 4; auto lambda = [a, b]{ std::cout << a + b << std::endl; };。
- 引用捕获[&x]或[&x, &y, &z]等：按引用捕获指定的外部变量。在 Lambda 函数内部对这些变量的修改会影响外部的原始变量。例如，int m = 5; int n = 6; auto lambda = [&m, &n]{ m++; n++; std::cout << m + n << std::endl; };。
- 默认值捕获[=]：按值捕获 Lambda 表达式所在作用域内的所有变量。例如，int p = 7; int q = 8; auto lambda = [=]{ std::cout << p * q << std::endl; };。
- 默认引用捕获[&]：按引用捕获 Lambda 表达式所在作用域内的所有变量。例如，int r = 9; int s = 10; auto lambda = [&]{ r--; s--; std::cout << r + s << std::endl; };。这种方式需要谨慎使用，因为可能会导致意外的变量修改。