快速排序＆Lambda表达式

快速排序

912. 排序数组

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm> // 用于交换函数swapusing 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]小于等于参照点，就继续向右移动iwhile (i <= j && nums[i] <= flag) {i++;}// 从右向左找第一个小于参照点的元素// 只要i还在有效区间内（i <= j）且当前元素nums[j]大于等于参照点，就继续向左移动jwhile (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]内的随机索引iint 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) {// 先进行随机划分操作，得到划分点的索引posint 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; };。这种方式需要谨慎使用，因为可能会导致意外的变量修改。