第七章 排序（堆排序）
说明 堆排序（Heap Sort）是一种基于二叉堆数据结构的比较型排序算法。它是一种选择排序，其最坏情况下的时间复杂度为O(n log n)**，其中 n 是待排序元素的数量。堆排序不是稳定排序，但是原地排序（只需要常数级别的额外空间）**。堆排序的基本思想是将待排序的序列构造成一个最大堆或最小堆，这样就可以方便地取出最大值或最小值，然后将其与末尾元素交换，最后对剩下的 n-1 个元素重新调整成堆，重复这个过程直到所有元素都被排序。 在堆排序中，我们通常使用最大堆（大顶堆），即每个父节点的值都大于或等于其子节点的值。最小堆（小顶堆）则是每个父节点的值都小于或等于其子节点的值。 代码这里假设堆数组元素下标从0开始 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostream>#include <vector>//这里假设堆数组元素下标从0开始void...
博客搭建参考教程
在win10系统中利用阿里云服务器搭建个人博客Win10环境下基于Hexo的静态博客环境搭建，及其阿里云部署 | 阿汤笔迹 butterfly博客主题配置Butterfly 文檔(三) 主題配置 | Butterfly 公安备案如何填写公安联网备案公安联网备案信息指南_备案(ICP Filing)-阿里云帮助中心 Markdown官方教程 Markdown 官方教程
《博弈论的诡计》提及的几种博弈
囚徒困境囚徒困境（Prisoner’s Dilemma）是博弈论中的一个经典问题，用来描述两个个体在面对合作或背叛选择时的策略互动。它展示了为什么即使双方合作可以得到更好的结果，但在某些情况下，个人可能会选择不合作的行为。 囚徒困境的基本设定：假设有两个犯罪嫌疑人被警方逮捕，并分别关押审讯，无法沟通。警方没有足够的证据定罪他们所涉嫌的主要犯罪，但有足够的证据以较轻的罪名给他们定罪。为了鼓励两人自首，警方给出以下条件： 如果两人都保持沉默（合作），则他们会因为较小的罪行各被判1年监禁。 如果一方揭发（背叛）另一方而另一方保持沉默，则揭发者将被释放，而保持沉默的一方将被判5年监禁。 如果两人都互相揭发（互相背叛），那么他们都会因中等程度的罪行被判3年监禁。 用支付矩阵表示就是： 合作 (沉默) 背叛 (揭发) 合作 -1, -1 -5, 0 背叛 0, -5 -3,...
C++实训项目
C++课程实训大作业的Github仓库
猜数游戏
一次猜测12345678910111213141516171819202122use std::io;//prelude预导入fn main() { println!("猜数!"); println!("猜测一个数"); let mut foo =1 ;//加上mut后说明变量是可变的 let bar = foo;//rust里所有变量默认情况下是不可变的（immutable） let mut guess = String::new(); io::stdin().read_line(&mut guess).expect("无法读取行"); //stdin()返回一个std::io::Stdin实例，该实例代表标准输入 /*read_line()方法从标准输入读取一行输入，将读取到的字符串存储在guess变量中 *同时返回一个io::Result<usize>，该类型表示一个结果，其中usize表示读取的字节数 ...
创建rust项目
Hello,World!创建文件夹在cmd终端操作(首先打开即将创建的文件夹想要的路径) 1234mkdir projectscd projectsmkdir hello_worldcd hello_world 更改文件名 1mv hello_world.rs main.rs 编译并运行这个文件 12rustc main.rs.\main.exe hello world 1234fn main(){ println!("Hello World");//println!是一个rust macro（宏）} 运行rust程序之前必须先编译 .pdb文件包含调试信息 Hello,Cargo使用cargo创建项目 1cargo new hello_cargo 为发布构建 1cargo build --release 建议尽量使用cargo
哈希表探测(作业)
要求比较线性探测、平方探测和立方探测产生的冲突数量 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include<iostream>#include<cmath>#include<vector>#include<ctime>using namespace std;const int SIZE = 9001;//大于9000的最小素数const int MAX = 4500;//放入的数据数量int lCollision = 0;int qCollision = 0;int cCollision = 0;int main(){ vector<int>linear(SIZE,...
第七章 排序(归并排序)
归并排序（Merge Sort）是一种分治算法，它将数组分成两半，递归地对每一半进行排序，然后再合并两个已排序的子数组得到最终的排序结果。 完整代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include<iostream>#include<vector>#include<cstring>#include<cstdio>using namespace std;template<typename Comp>void merge(vector<Comp>& a, vector<Comp>& tmpArray, int left,int right){ int mid, i, j; int k, l, target; mid =...
第七章 排序(冒泡、选排、插排、希尔排序)
冒泡排序1234567891011121314//冒泡排序，a为vector数组//从小到大排序for (int i = 0; i < a.size() - 1; i++){ for (int j = 0; j < a.size() - 1 - i; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } }} 选择排序12345678910111213141516//选择排序,a为vector数组int min;//存储每个循环里的最小值的下标for (int i = 0; i < a.size() - 1; i++){ min = i; for (int j = i+1; j < a.size(); j++) { if (a[j] < a[min])min = j; } if (min != i) { int...
第七章 排序（快排）
常用快排模板12345678910111213141516void quick_sort(int q[], int l, int r){ if(l>=r)return; int x=q[(l+r)/2],i=l-1,j=r+1; while(i<j) { do i++;while(q[i]<x); do j--;while(q[j]>x); if(i<j) { swap(q[i],q[j]); } } quick_sort(q,l,j); ...
