数据结构与算法（八）：排序算法

参考引用

  • Hello 算法
  • Github：hello-algo

1. 选择排序

  • 选择排序的工作原理非常直接：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾，设数组的长度为 n
    • 初始状态下，所有元素未排序，即未排序（索引）区间为 [0, n-1]
    • 选取区间 [0, n-1] 中的最小元素，将其与索引 0 处元素交换。完成后，数组前 1 个元素已排序
    • 选取区间 [1, n-1] 中的最小元素，将其与索引 1 处元素交换。完成后，数组前 2 个元素已排序
    • 以此类推。经过 n-1 轮选择与交换后，数组前 n-1 个元素已排序
    • 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成
/* 选择排序 */
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
void selectionSort(vector<int> &nums) {int n = nums.size();// 外循环：未排序区间为 [i, n-1]for (int i = 0; i < n - 1; i++) {// 内循环：找到未排序区间内的最小元素int k = i;for (int j = i + 1; j < n; j++) {if (nums[j] < nums[k])k = j; // 记录最小元素的索引}// 将该最小元素与未排序区间的首个元素交换swap(nums[i], nums[k]);}
}

2. 冒泡排序

  • 冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大小，如果 “左元素 > 右元素” 就交换它俩。遍历完成后，最大的元素会被移动到数组的最右端

算法流程

  • 设数组的长度为 n，冒泡排序的步骤如下图所示
    • 首先，对 n 个元素执行 “冒泡”，将数组的最大元素交换至正确位置
    • 接下来，对剩余 n-1 个元素执行 “冒泡”，将第二大元素交换至正确位置
    • 以此类推，经过 n-1 轮 “冒泡” 后，前 n-1 大的元素都被交换至正确位置
    • 仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成

在这里插入图片描述

/* 冒泡排序（标志优化）*/
// 时间复杂度：O(n^2)，引入 flag 优化后，最佳时间复杂度可达到 O(n)
// 空间复杂度：O(1)
void bubbleSortWithFlag(vector<int> &nums) {// 外循环：未排序区间为 [0, i]，控制冒泡排序的轮数for (int i = nums.size() - 1; i > 0; i--) {bool flag = false; // 初始化标志位，用于标志当前轮次是否有元素交换的标志位// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端for (int j = 0; j < i; j++) {if (nums[j] > nums[j + 1]) {// 交换 nums[j] 与 nums[j + 1]// 这里使用了 std::swap() 函数swap(nums[j], nums[j + 1]);flag = true; // 记录交换元素}}if (!flag)break; // 此轮冒泡未交换任何元素，即数组已经是有序的，直接跳出}
}

3. 插入排序

  • 插入排序的工作原理与手动整理一副牌的过程非常相似。具体来说，在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置

  • 下图展示了数组插入元素的操作流程。设基准元素为 base ，需要将从目标索引到 base 之间的所有元素向右移动一位，然后再将 base 赋值给目标索引

在这里插入图片描述

3.1 算法流程

  • 初始状态下，数组的第 1 个元素已完成排序
  • 选取数组的第 2 个元素作为 base，将其插入到正确位置后，数组的前 2 个元素已排序
  • 选取第 3 个元素作为 base，将其插入到正确位置后，数组的前 3 个元素已排序
  • 以此类推，在最后一轮中，选取最后一个元素作为 base ，将其插入到正确位置后，所有元素均已排序

在这里插入图片描述

/* 插入排序 */
// 时间复杂度：O(n^2)，当输入数组完全有序时为 O(n)
// 空间复杂度：O(1)
void insertionSort(vector<int> &nums) {// 外循环：已排序元素数量为 1, 2, ..., nfor (int i = 1; i < nums.size(); i++) {int base = nums[i], j = i - 1;// 内循环：将 base 插入到已排序部分的正确位置while (j >= 0 && nums[j] > base) {nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位j--;}nums[j + 1] = base; // 将 base 赋值到正确位置}
}

3.2 插入排序优势

  • 插入排序的时间复杂度为 O(n^2)，而快速排序的时间复杂度为 O(nlog n)

    • 尽管插入排序的时间复杂度相比快速排序更高，但在数据量较小的情况下，n^2 和 nlog n 数值接近，插入排序通常更快

  • 实际情况中，插入排序的使用频率显著高于冒泡排序和选择排序

    • 冒泡排序基于元素交换实现，需要借助一个临时变量，共涉及 3 个单元操作；插入排序基于元素赋值实现，仅需 1 个单元操作。因此，冒泡排序的计算开销通常比插入排序更高
    • 选择排序在任何情况下的时间复杂度都为 O(n^2)。如果给定一组部分有序的数据，插入排序通常比选择排序效率更高
    • 选择排序不稳定，无法应用于多级排序

4. 快速排序

  • 快速排序是一种基于分治策略的排序算法
  • 快速排序的核心操作是 “哨兵划分”，其目标是：选择数组中的某个元素作为 “基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧
    • 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端
    • 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素
    • 循环执行步骤 2，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线

    哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题

    • 哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足 “左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”。因此，接下来只需对这两个子数组进行排序

在这里插入图片描述

/* 元素交换 */
void swap(vector<int> &nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;
}/* 哨兵划分 */
int partition(vector<int> &nums, int left, int right) {// 以 nums[left] 作为基准数int i = left, j = right;while (i < j) {while (i < j && nums[j] >= nums[left])j--;          // 从右向左找首个小于基准数的元素while (i < j && nums[i] <= nums[left])i++;          // 从左向右找首个大于基准数的元素swap(nums, i, j); // 交换这两个元素}swap(nums, i, left);  // 将基准数交换至两子数组的分界线return i;             // 返回基准数的索引
}

4.1 算法流程

  • 首先，对原数组执行一次 “哨兵划分”，得到未排序的左子数组和右子数组
  • 然后，对左子数组和右子数组分别递归执行 “哨兵划分”
  • 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序

在这里插入图片描述

/* 快速排序 */
// 时间复杂度：O(nlog n)，最差情况下 O(n^2)
// 空间复杂度：O(n)
void quickSort(vector<int> &nums, int left, int right) {// 子数组长度为 1 时终止递归if (left >= right)return;// 哨兵划分int pivot = partition(nums, left, right);// 递归左子数组、右子数组quickSort(nums, left, pivot - 1);quickSort(nums, pivot + 1, right);
}

4.2 快排为什么快

  • 快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与 “归并排序” 和 “堆排序” 相同，但通常快速排序的效率更高，主要有以下原因
    • 出现最差情况的概率很低
      • 虽然快速排序的最差时间复杂度为 O(n^2)，没有归并排序稳定，但在绝大多数情况下，快速排序能在 O(nlog n) 的时间复杂度下运行
    • 缓存使用效率高
      • 在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像 “堆排序” 这类算法需要跳跃式访问元素，从而缺乏这一特性
    • 复杂度的常数系数低
      • 在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与 “插入排序” 比 “冒泡排序” 更快的原因类似

4.3 基准数优化

  • 快速排序在某些输入下的时间效率可能降低

    • 例如：假设输入数组是完全倒序的，由于选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 n-1、右子数组长度为 0。如此递归下去，每轮哨兵划分后的右子数组长度都为 0，分治策略失效，快速排序退化为 “冒泡排序”

  • 为避免这种情况发生，可以优化哨兵划分中的基准数的选取策略

    • 例如，可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意
    • 可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。这样，基准数 “既不太小也不太大” 的概率将大幅提升。还可以选取更多候选元素，以进一步提高算法的稳健性
    /* 选取三个元素的中位数 */
int medianThree(vector<int> &nums, int left, int mid, int right) {// 此处使用异或运算来简化代码// 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))return left;else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))return mid;elsereturn right;
}/* 哨兵划分（三数取中值） */
int partition(vector<int> &nums, int left, int right) {// 选取三个候选元素的中位数int med = medianThree(nums, left, (left + right) / 2, right);// 将中位数交换至数组最左端swap(nums, left, med);// 以 nums[left] 作为基准数int i = left, j = right;while (i < j) {while (i < j && nums[j] >= nums[left])j--; // 从右向左找首个小于基准数的元素while (i < j && nums[i] <= nums[left])i++;          // 从左向右找首个大于基准数的元素swap(nums, i, j); // 交换这两个元素}swap(nums, i, left); // 将基准数交换至两子数组的分界线return i;            // 返回基准数的索引
}

4.4 尾递归优化

  • 在某些输入下，快速排序可能占用空间较多
    • 以完全倒序的输入数组为例，由于每轮哨兵划分后右子数组长度为 0，递归树的高度会达到 n-1，此时需要占用 O(n) 大小的栈帧空间
  • 为了防止栈帧空间的累积，可以在每轮哨兵排序完成后，比较两个子数组的长度
    • 仅对较短的子数组进行递归。由于较短子数组的长度不会超过 n/2，因此这种方法能确保递归深度不超过 log n，从而将最差空间复杂度优化至 O(log n)
    /* 快速排序（尾递归优化） */
void quickSort(vector<int> &nums, int left, int right) {// 子数组长度为 1 时终止while (left < right) {// 哨兵划分操作int pivot = partition(nums, left, right);// 对两个子数组中较短的那个执行快排if (pivot - left < right - pivot) {quickSort(nums, left, pivot - 1); // 递归排序左子数组left = pivot + 1;                 // 剩余未排序区间为 [pivot + 1, right]} else {quickSort(nums, pivot + 1, right); // 递归排序右子数组right = pivot - 1;                 // 剩余未排序区间为 [left, pivot - 1]}}
}

5. 归并排序

  • 归并排序是一种基于分治策略的排序算法，包含下图所示的 “划分” 和 “合并” 阶段
    • 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题
    • 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束

在这里插入图片描述

5.1 算法流程

  • “划分阶段” 从顶至底递归地将数组从中点切分为两个子数组
    • 计算数组中点 mid，递归划分左子数组（区间 [left, mid]）和右子数组（区间 [mid + 1, right]）
    • 递归执行步骤 1，直至子数组区间长度为 1 时，终止递归划分
  • “合并阶段” 从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为 1 的子数组开始合并，合并阶段中的每个子数组都是有序的

在这里插入图片描述

  • 归并排序与二叉树后序遍历的递归顺序是一致的
    • 后序遍历：先递归左子树，再递归右子树，最后处理根节点
    • 归并排序：先递归左子数组，再递归右子数组，最后处理合并
    /* 合并左子数组和右子数组 */
// 左子数组区间 [left, mid]
// 右子数组区间 [mid + 1, right]
void merge(vector<int> &nums, int left, int mid, int right) {// 初始化辅助数组vector<int> tmp(nums.begin() + left, nums.begin() + right + 1);// 左子数组的起始索引和结束索引int leftStart = left - left, leftEnd = mid - left;// 右子数组的起始索引和结束索引int rightStart = mid + 1 - left, rightEnd = right - left;// i, j 分别指向左子数组、右子数组的首元素int i = leftStart, j = rightStart;// 通过覆盖原数组 nums 来合并左子数组和右子数组for (int k = left; k <= right; k++) {// 若“左子数组已全部合并完”，则选取右子数组元素，并且 j++if (i > leftEnd)nums[k] = tmp[j++];// 否则，若“右子数组已全部合并完”或“左子数组元素 <= 右子数组元素”，则选取左子数组元素，并且 i++else if (j > rightEnd || tmp[i] <= tmp[j])nums[k] = tmp[i++];// 否则，若“左右子数组都未全部合并完”且“左子数组元素 > 右子数组元素”，则选取右子数组元素，并且 j++elsenums[k] = tmp[j++];}
}/* 归并排序 */
// 时间复杂度：O(nlog n)
// 空间复杂度：O(n)
void mergeSort(vector<int> &nums, int left, int right) {// 终止条件if (left >= right)return; // 当子数组长度为 1 时终止递归// 划分阶段int mid = (left + right) / 2;    // 计算中点mergeSort(nums, left, mid);      // 递归左子数组mergeSort(nums, mid + 1, right); // 递归右子数组// 合并阶段merge(nums, left, mid, right);
}

merge() 函数注意事项

  • nums 的待合并区间为 [left, right] ，但由于 tmp 仅复制了 nums 该区间的元素，因此 tmp 对应区间为 [0, right - left]
  • 在比较 tmp[i] 和 tmp[j] 的大小时，还需考虑子数组遍历完成后的索引越界问题，即 i > leftEnd 和 j > rightEnd 的情况。索引越界的优先级是最高的，如果左子数组已经被合并完了，那么不需要继续比较，直接合并右子数组元素即可

6. 堆排序

  • 堆排序是一种基于堆数据结构实现的高效排序算法。可利用 “建堆操作” 和 “元素出堆操作” 实现堆排序
    • 输入数组并建立小顶堆，此时最小元素位于堆顶
    • 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列

    以上方法虽然可行，但需要借助一个额外数组来保存弹出的元素，比较浪费空间

算法流程

  • 1、输入数组并建立大顶堆
    • 完成后，最大元素位于堆顶
  • 2、将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换
    • 完成交换后，堆的长度减 1，已排序元素数量加 1
  • 3、从堆顶元素开始，从顶到底执行堆化操作
    • 完成堆化后，堆的性质得到修复
  • 4、循环执行第 2 和 3 步
    • 循环 n-1 轮后，即可完成数组排序

在这里插入图片描述

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(vector<int> &nums, int n, int i) {while (true) {// 判断节点 i, l, r 中值最大的节点，记为 maint l = 2 * i + 1;int r = 2 * i + 2;int ma = i;if (l < n && nums[l] > nums[ma])ma = l;if (r < n && nums[r] > nums[ma])ma = r;// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出if (ma == i) {break;}// 交换两节点swap(nums[i], nums[ma]);// 循环向下堆化i = ma;}
}/* 堆排序 */
// 时间复杂度：O(nlog n)
// 空间复杂度：O(1)
void heapSort(vector<int> &nums) {// 建堆操作：堆化除叶节点以外的其他所有节点for (int i = nums.size() / 2 - 1; i >= 0; --i) {siftDown(nums, nums.size(), i);}// 从堆中提取最大元素，循环 n-1 轮for (int i = nums.size() - 1; i > 0; --i) {// 交换根节点与最右叶节点（即交换首元素与尾元素）swap(nums[0], nums[i]);// 以根节点为起点，从顶至底进行堆化siftDown(nums, i, 0);}
}

7. 桶排序

  • 前述的几种排序算法都属于 “基于比较的排序算法”，它们通过比较元素间的大小来实现排序。此类排序算法的时间复杂度无法超越 O(nlog n)。接下来，将探讨几种 “非比较排序算法”，它们的时间复杂度可以达到线性阶
  • 桶排序是分治策略的一个典型应用
    • 它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中
    • 然后，在每个桶内部分别执行排序
    • 最终按照桶的顺序将所有数据合并

算法流程

  • 考虑一个长度为 n 的数组，元素是范围 [0, 1) 的浮点数
    • 初始化 k 个桶，将 n 个元素分配到 k 个桶中
    • 对每个桶分别执行排序
    • 按照桶的从小到大的顺序，合并结果

在这里插入图片描述

/* 桶排序 */
// 时间复杂度：O(n + k)，最差（所有元素被分至同一个桶中）时间复杂度是 O(n^2)
// 空间复杂度：O(n + k)
void bucketSort(vector<float> &nums) {// 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素int k = nums.size() / 2;vector<vector<float>> buckets(k);// 1. 将数组元素分配到各个桶中for (float num : nums) {// 输入数据范围 [0, 1)，使用 num * k 映射到索引范围 [0, k-1]int i = num * k;// 将 num 添加进桶 bucket_idxbuckets[i].push_back(num);}// 2. 对各个桶执行排序for (vector<float> &bucket : buckets) {// 使用内置排序函数，也可以替换成其他排序算法sort(bucket.begin(), bucket.end());}// 3. 遍历桶合并结果int i = 0;for (vector<float> &bucket : buckets) {for (float num : bucket) {nums[i++] = num;}}
}

8. 小结

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/153013.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

HTTP协议的请求协议和响应协议的组成,HTTP常见的状态信息

HTTP协议的请求协议和响应协议的组成,HTTP常见的状态信息

HTTP协议 什么是协议 协议实际上是某些人或组织提前制定好的一套规范,大家只要都按照这个规范来就可以做到沟通无障碍 HTTP协议是W3C(万维网联盟组织)制定的一种超文本传输通信协议(发送消息的模板和数据的格式),除了传送字符串,还有声音、视频、图片等流媒体等超文本信息 …
阅读更多...
伦敦银最新走势不利怎么办

伦敦银最新走势不利怎么办

跟其他的投资品种一样&#xff0c;伦敦银的价格走势在不停的变化&#xff0c;而且由于本身产品具有较高的资金杠杆&#xff0c;所以万一行情走势变得不利&#xff0c;在很短的时间之内就会对投资者的账户造成严重损失&#xff0c;所以投资者应该对此作好充分的准备。 伦敦银的最…
阅读更多...
LabVIEW利用以太网开发智能液位检测仪

LabVIEW利用以太网开发智能液位检测仪

LabVIEW利用以太网开发智能液位检测仪 目前&#xff0c;工业以太网接口在国内外的发展已经达到了相当深入的程度&#xff0c;特别是在自动化控制和工业控制领域有着非常广泛的应用。在工业生产过程中&#xff0c;钢厂的连铸机是前后的连接环节&#xff0c;其中钢水从大钢包进入…
阅读更多...
Spring Boot如何配置CORS支持

Spring Boot如何配置CORS支持

Spring Boot如何配置CORS支持 CORS&#xff08;跨源资源共享&#xff09;是一种Web浏览器的安全性功能&#xff0c;用于控制网页上的脚本文件从不同的源加载其他网页资源。在开发现代Web应用程序时&#xff0c;通常需要跨域请求不同的资源&#xff0c;如API服务或其他Web应用程…
阅读更多...
一个tomcat下如何部署多个项目？

一个tomcat下如何部署多个项目？

1、不修改端口&#xff0c;部署多个项目 清楚tomcat目录结构的应该都知道&#xff0c;项目包是放在webapps目录下的&#xff0c;那能否在同一个tomcat的webapps目录下运行多个不同项目呢&#xff1f; 答案是可以的。 1、将多个项目包放入webapps文件夹下 2、修改conf下的serv…
阅读更多...
reactjs开发环境搭建

reactjs开发环境搭建

Reactjs是一个前端web页面应用开发框架工具集&#xff0c;其支持前端构建页面以及后端构建页面两种常用的开发场景&#xff0c;其中&#xff0c;支持reactjs的开发框架包括next.js、remix、gatsby以及其他&#xff0c;本文主要描述next.js开发环境的搭建&#xff0c;next.js是一…
阅读更多...
Verilog HDL阻塞赋值和非阻塞赋值笔记

Verilog HDL阻塞赋值和非阻塞赋值笔记

1. module test( input wire clk, input wire b, output reg a, output reg c ); always(posedge clk) begin ab; ca; end endmodule 上面的代码在vivado中综合后的电路为&#xff1a; 2. module test( input wire clk, input wire b, outp…
阅读更多...
springcloud之项目实战环境准备

springcloud之项目实战环境准备

写在前面 为了更好的学习springcloud&#xff0c;我们来一起开发一个实战项目&#xff0c;加深理解。 1&#xff1a;项目介绍 在开始项目实战之前先来做一个整体的项目介绍&#xff0c;从而能够让对项目的整体架构和模板有一个比较清晰的认知。 大家都知道双11&#xff0c;…
阅读更多...
JS进阶-原型

JS进阶-原型

原型 原型就是一个对象&#xff0c;也称为原型对象 构造函数通过原型分配的函数是所有对象所共享的 JavaScript规定&#xff0c;每一个构造函数都有一个prototype属性&#xff0c;指向另一个对象&#xff0c;所以我们也称为原型对象 这个对象可以挂载函数&#xff0c;对象实…
阅读更多...
64.最小路径和

64.最小路径和

法&#xff1a;动态规划 第一行的元素&#xff0c;只有通过左侧右移才能到达&#xff1b;第一列的元素&#xff0c;只有通过上方的下移才能到达。其他位置元素&#xff1a;比较从上方元素向下移动的路径和和左侧元素向右移动的路径和的较小值dp[i][j]&#xff1a;到达(i,j)位置…
阅读更多...
中国移动咪咕、阿里云、华为“秀肌肉”，这届亚运会的“高光”不止比赛

中国移动咪咕、阿里云、华为“秀肌肉”，这届亚运会的“高光”不止比赛

文 | 智能相对论 作者 | 青月 竞技体育的发展&#xff0c;其实也可以看作是一部“技术进化史”。 在1924年的巴黎&#xff0c;广播首次进入奥运会&#xff0c;人们第一次可以通过报纸以外的方式了解奥运会。 1928年&#xff0c;在荷兰申办的阿姆斯特丹奥运会&#xff0c;高…
阅读更多...
【jvm--方法区】

【jvm--方法区】

文章目录 1. 栈、堆、方法区的交互关系2. 方法区的内部结构3. 运行时常量池4. 方法区的演进细节5. 方法区的垃圾回收 1. 栈、堆、方法区的交互关系 方法区的基本理解&#xff1a; 方法区&#xff08;Method Area&#xff09;与 Java 堆一样&#xff0c;是各个线程共享的内存区…
阅读更多...
【力扣】单调栈：901. 股票价格跨度

【力扣】单调栈：901. 股票价格跨度

【力扣】单调栈&#xff1a;901. 股票价格跨度 文章目录 【力扣】单调栈&#xff1a;901. 股票价格跨度1. 题目介绍2. 思路3. 解题代码参考 1. 题目介绍 设计一个算法收集某些股票的每日报价&#xff0c;并返回该股票当日价格的 跨度 。 当日股票价格的 跨度 被定义为股票价格…
阅读更多...
75.颜色分类

75.颜色分类

原地排序&#xff1a;空间复杂度为1 class Solution { public:void sortColors(vector<int>& nums) {if(0){//法一&#xff1a;单指针两个遍历int nnums.size();int ptr0;for(int i0;i<n;i){if(nums[i]0){swap(nums[i],nums[ptr]);ptr;}}for(int iptr;i<n;i){…
阅读更多...
【Proteus仿真】【STM32单片机】汽车倒车报警系统设计

【Proteus仿真】【STM32单片机】汽车倒车报警系统设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真STM32单片机控制器&#xff0c;使用LCD1602液晶、按键、继电器电机模块、DS18B20温度传感器、蜂鸣器LED、HCSR04超声波等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显…
阅读更多...
2021年03月 Python（二级）真题解析#中国电子学会#全国青少年软件编程等级考试

2021年03月 Python（二级）真题解析#中国电子学会#全国青少年软件编程等级考试

Python编程&#xff08;1~6级&#xff09;全部真题・点这里 一、单选题&#xff08;共25题&#xff0c;每题2分&#xff0c;共50分&#xff09; 第1题 对于字典infor {“name”:“tom”, “age”:13, “sex”:“male”}&#xff0c;删除"age":13键值对的操作正确的…
阅读更多...
数据压缩与管理：掌握Linux VDO和LVM的力量

数据压缩与管理：掌握Linux VDO和LVM的力量

1.逻辑卷(LVM&#xff0c;Logical Volume Management) 动态的为服务器磁盘添加空间&#xff0c;而不会影响原磁盘的数据&#xff0c;也不需要对原始磁盘重新分区。 1.1 LVM介绍 以下是LVM的示意图&#xff1a; 我们拿到一块硬盘后首先对齐进行划分分区&#xff0c;也就得到…
阅读更多...
Godot2D角色导航教程（角色随鼠标移动）

Godot2D角色导航教程（角色随鼠标移动）

文章目录 运行结果2D导航概述开始前的准备2D导航创建导航网格创建角色 其他文章 运行结果 2D导航概述 Godot为2D和3D游戏提供了多个对象、类和服务器&#xff0c;以便于基于网格或基于网格的导航和路径查找。 说到导航&#xff0c;就得说一下导航网格&#xff0c;导航网格定义…
阅读更多...
arm-三盏灯流水

arm-三盏灯流水

.text .global _start _start: 1.设置GPIOE寄存器的时钟使能 RCC_MP_AHB4ENSETR[4]->1 0x50000a28 LDR R0,0x50000A28 LDR R1,[R0] ORR R1,R1,#(0x3<<4) 第四位第五位都设置为1 STR R1,[R0] 写回2.设置PE10管脚为输出模式 GPIOE_MODER[21:20]->01 0x5000…
阅读更多...
Cuckoo沙箱各Ubuntu版本安装及使用

Cuckoo沙箱各Ubuntu版本安装及使用

1.沙箱简介 1.1 沙箱 沙箱是一个虚拟系统程序&#xff0c;允许你在沙箱环境中运行浏览器或其他程序&#xff0c;因此运行所产生的变化可以随后删除。它创造了一个类似沙盒的独立作业环境&#xff0c;在其内部运行的程序并不能对硬盘产生永久性的影响。 在网络安全中&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023