https://www.guwolf.com/author/1/ GuWolf https://www.guwolf.com/archives/nginx-brotli.html 2025-08-25T21:07:00+08:00 什么是Brotli ?Brotli是Google在2015年推出的压缩算法，目前各大浏览器均已支持Brotli，相比Gzip，有着更高的压缩率(尤其在处理CSS、JS、HTML这类文件)，解压速度却相差无几，这意味着它有着更小的数据传输量，对于网络环境较差、带宽受限的用户或移动端访问者而言，能直接转化为更快的页面加载速度和更流畅的交互体验。所以对于弱网环境下(如跨国传输)，一个可行的优化思路是优先使用Brotli，对于不支持Brotli的浏览器，再回退到Gzip。当然，更高的压缩率比如会带来压缩时更大的CPU开销，所以我们接下来也会介绍预压缩这种解决方案来缓解这个问题。启用Brotli编译具有brotli模块的Nginx获取源代码先克隆ngx\_brotli源代码到本地git clone始化和同步ngx\_brotli的子模块cd ngx_brotli && git submodule update --init下载Nginx的源码并解压wget https://nginx.org/download/nginx-1.28.0.tar.gz && tar zxvf nginx-1.28.0.tar.gz保留原编译参数并编译安装依赖库apt update && apt install libbrotli-dev进入源代码目录cd nginx-1.28.0首先查看当前的Nginx编译参数nginx -V生成Makefile并编译./configure [原参数] --add-module=[ngx_brotli路径] make编译好的二进制在 objs/nginx ，先把原来的nginx二进制复制一份用于防止意外，然后替换原来的二进制文件编辑nginx配置文件在http块下加入http { ... brotli on; brotli_comp_level 6; brotli_min_length 512; brotli_types text/plain text/javascript text/css text/xml text/x-component font/opentype application/json; brotli_static on; ...参数解释指令名称语法格式默认值作用域描述重要参数说明brotli_staticon , off , alwaysoffhttp, server, location启用/禁用预压缩文件(.br)检测-on：客户端支持Brotli时返回.br文件- always：强制返回.br文件（无论客户端是否支持）brotlion , offoffhttp, server, location, if启用/禁用动态响应压缩需与brotli_types配合使用brotli_types [mime_type ...] , *text/htmlhttp, server, location指定启用压缩的MIME类型-*：压缩所有类型- text/html 始终被压缩（无需声明）brotli_buffers -http, server, location已废弃（配置会被忽略）历史遗留参数，无实际作用brotli_comp_level``6http, server, location设置动态压缩级别范围：0-11- 0：最快（最低压缩）- 11：最慢（最高压缩）brotli_window``512khttp, server, location设置滑动窗口大小（影响压缩率和内存）有效值：1k,2k,4k,8k,16k,32k,64k,128k,256k,512k,1m,2m,4m,8m,16mbrotli_min_length``20http, server, location设置启用压缩的最小响应长度（仅依据Content-Length头）单位：字节建议值：≥256（避免小文件压缩得不偿失）处理Brotli预压缩预压缩可以减少CPU开销，由于动态压缩会在每次请求(尤其是高并发下)对CPU造成压力，无论你是想优化并发性能还是想得到更高的压缩率，都建议使用Brotli预压缩，在打开了 brotli_static 项的时候nginx会先检测当前访问的文件是否有 .br 的预压缩文件并返回 (如果有的话，直接返回预压缩文件，没有的话再根据 brotli 项是否开启，决定是否进行动态压缩)。所以我们可以写一个脚本去处理预压缩#!/bin/bash WEB_ROOT="/aaa/www" 网页根目录 COMP_LEVEL=11 # 压缩级别 (0-11) LOG_FILE="/var/log/br.log" #存储日志的路径 # 创建日志目录 mkdir -p "$(dirname "$LOG_FILE")" # 查找需要压缩的文件 find "$WEB_ROOT" -type f \( \ -name "*.html" -o \ -name "*.css" -o \ -name "*.js" -o \ -name "*.xml" -o \ -name "*.json" -o \ -name "*.svg" -o \ -name "*.ttf" -o \ -name "*.woff" -o \ -name "*.woff2" \ \) | while read -r file; do # 跳过已压缩文件（如果源文件未修改） if [ -f "$file.br" ] && [ "$file" -ot "$file.br" ]; then continue fi # 记录压缩开始时间 start_time=$(date +%s) # 执行压缩（修正后的命令） brotli --quality="$COMP_LEVEL" --force --keep --output="$file.br" "$file" # 记录压缩结果 end_time=$(date +%s) orig_size=$(stat -c%s "$file") comp_size=$(stat -c%s "$file.br") ratio=$(echo "scale=2; $comp_size * 100 / $orig_size" | bc) echo "[$(date '+%Y-%m-%d %H:%M:%S')] Compressed: $file" >> "$LOG_FILE" echo " Original: $orig_size bytes, Compressed: $comp_size bytes, Ratio: ${ratio}%" >> "$LOG_FILE" echo " Time taken: $((end_time - start_time)) seconds" >> "$LOG_FILE" echo "----------------------------------------" >> "$LOG_FILE" done echo "Completed. Log saved to: $LOG_FILE"这样，在每次文件发生变化的时候都运行一次，我们就可以使用最高的压缩率和最小的CPU开销来响应请求了。 https://www.guwolf.com/archives/codeserver_font.html 2025-07-30T18:55:00+08:00 实现原理我们可以通过CSS注入来使得浏览器加载需要的字体文件, 以JetBrains Mono为例详细步骤准备字体文件从JetBrains Mono官网下载字体文件，并把woff和woff2格式的字体文件放置在fonts目录，并把fonts目录移到code-server安装路径下的 lib/vscode/out/vs/code/browser/workbench 位置。以下是目录树/usr/lib/code-server/lib/vscode/out/vs/code/browser/workbench ├── fonts │ ├── JetBrainsMono-Bold-Italic.woff │ ├── JetBrainsMono-Bold-Italic.woff2 │ ├── JetBrainsMono-Bold.woff │ ├── JetBrainsMono-Bold.woff2 │ ├── JetBrainsMono-ExtraBold-Italic.woff │ ├── JetBrainsMono-ExtraBold-Italic.woff2 │ ├── JetBrainsMono-ExtraBold.woff │ ├── JetBrainsMono-ExtraBold.woff2 │ ├── JetBrainsMono-Italic.woff │ ├── JetBrainsMono-Italic.woff2 │ ├── JetBrainsMono-Medium-Italic.woff │ ├── JetBrainsMono-Medium-Italic.woff2 │ ├── JetBrainsMono-Medium.woff │ ├── JetBrainsMono-Medium.woff2 │ ├── JetBrainsMono-Regular.woff │ └── JetBrainsMono-Regular.woff2创建css文件新建一个 fonts.css 放在code-server安装路径下的 lib/vscode/out/vs/code/browser/workbench 位置我的是 /usr/lib/code-server/lib/vscode/out/vs/code/browser/workbench@font-face { font-family: 'JetBrains Mono'; src: url('fonts/JetBrainsMono-Regular.woff2') format('woff2'), url('fonts/JetBrainsMono-Regular.woff') format('woff'); font-weight: 400; font-style: normal; } @font-face { font-family: 'JetBrains Mono'; src: url('fonts/JetBrainsMono-Italic.woff2') format('woff2'), url('fonts/JetBrainsMono-Italic.woff') format('woff'); font-weight: 400; font-style: italic; } /* 可根据需要添加更多字重和样式 */ /* @font-face { font-family: 'JetBrains Mono'; src: url('fonts/JetBrainsMono-Medium.woff2') format('woff2'), url('fonts/JetBrainsMono-Medium.woff') format('woff'); font-weight: 500; font-style: normal; } @font-face { font-family: 'JetBrains Mono'; src: url('fonts/JetBrainsMono-Medium-Italic.woff2') format('woff2'), url('fonts/JetBrainsMono-Medium-Italic.woff') format('woff'); font-weight: 500; font-style: italic; } @font-face { font-family: 'JetBrains Mono'; src: url('fonts/JetBrainsMono-Bold.woff2') format('woff2'), url('fonts/JetBrainsMono-Bold.woff') format('woff'); font-weight: 700; font-style: normal; } @font-face { font-family: 'JetBrains Mono'; src: url('fonts/JetBrainsMono-Bold-Italic.woff2') format('woff2'), url('fonts/JetBrainsMono-Bold-Italic.woff') format('woff'); font-weight: 700; font-style: italic; } @font-face { font-family: 'JetBrains Mono'; src: url('fonts/JetBrainsMono-ExtraBold.woff2') format('woff2'), url('fonts/JetBrainsMono-ExtraBold.woff') format('woff'); font-weight: 800; font-style: normal; } @font-face { font-family: 'JetBrains Mono'; src: url('fonts/JetBrainsMono-ExtraBold-Italic.woff2') format('woff2'), url('fonts/JetBrainsMono-ExtraBold-Italic.woff') format('woff'); font-weight: 800; font-style: italic; } */修改 workbench.html编辑工作台 HTML 文件，在 <head> 部分添加 CSS 引用：<link rel="stylesheet" href="{{WORKBENCH_WEB_BASE_URL}}/out/vs/code/browser/workbench/fonts.css">最终目录结构没有用到的字体可以不放/usr/lib/code-server/lib/vscode/out/vs/code/browser/workbench ├── callback.html ├── fonts │ ├── JetBrainsMono-Bold-Italic.woff │ ├── JetBrainsMono-Bold-Italic.woff2 │ ├── JetBrainsMono-Bold.woff │ ├── JetBrainsMono-Bold.woff2 │ ├── JetBrainsMono-ExtraBold-Italic.woff │ ├── JetBrainsMono-ExtraBold-Italic.woff2 │ ├── JetBrainsMono-ExtraBold.woff │ ├── JetBrainsMono-ExtraBold.woff2 │ ├── JetBrainsMono-Italic.woff │ ├── JetBrainsMono-Italic.woff2 │ ├── JetBrainsMono-Medium-Italic.woff │ ├── JetBrainsMono-Medium-Italic.woff2 │ ├── JetBrainsMono-Medium.woff │ ├── JetBrainsMono-Medium.woff2 │ ├── JetBrainsMono-Regular.woff │ └── JetBrainsMono-Regular.woff2 ├── fonts.css ├── workbench.css ├── workbench.html ├── workbench.js └── workbench.js.map设置编辑器字体修改setting.json的相关内容{ "editor.fontFamily": "'JetBrains Mono', Consolas, 'Courier New'", "editor.fontLigatures": true, //对于连字字体，一定要打开连字符功能 }注意: 对于连字字体，一定要打开fontLigatures 否则会出现光标错位问题此时，我的光标所在位置应该是行末最后效果 https://www.guwolf.com/archives/big-fenwick.html 2025-03-18T21:14:00+08:00 传统方法的局限在算法竞赛中，树状数组（Fenwick Tree）因其简洁高效的特性被广泛使用。但传统实现需要预先确定数据范围并预分配空间，当值域达到1e18量级时，离散化预处理会带来诸多不便：需要离线处理、增加编码复杂度。动态空间的黑魔法我们可以利用unordered_map的无序容器特性配合树状数组的跳跃特性，实现动态内存分配的树状数组，创建出一个1e18甚至更大的树状数组，可以省去离散化的步骤，同时无需离线#define LL long long unordered_map<LL, LL> tree; const LL N = 1e18 + 10; LL lowbit(LL x) {return x & -x;} void add(LL x, LL v) { while(x <= N) { tree[x] += v; x += lowbit(x); } } LL sum(LL x) { LL sum = 0; while(x) { sum += tree[x]; x -= lowbit(x); } return sum; }实现原理分析空间动态分配：unordered_map仅在访问时创建键值对，实际空间复杂度约为O(q logU)，其中q是操作次数，U是值域大小时间效率折衷：哈希表访问时间复杂度为均摊O(1)，但实际常数比普通数组大，在ICPC比赛中请分析好时间再谨慎使用。优势与代价✅ 优势：对于超大值域无需预处理，支持在线操作节省内存空间（稀疏数据场景）⚠️ 注意事项：时间复杂度常数较大哈希冲突导致时间复杂度最坏至O(n)（可参考自定义哈希篇）实战下面是使用超大树状数组做的题1D Country - AtCoder abc371\_d - Virtual Judge使用建议推荐在以下场景使用该技巧：值域极大但操作次数有限（q ≤ 1e5）需要快速实现原型的情况内存资源紧张的环境 https://www.guwolf.com/archives/2024zscpc.html 2024-12-09T11:03:00+08:00 感谢HXY提供了E、H题的题解A. Welcome to ZSCPC (签到大水题)解题思路今年是2024年，2024 - 2007 = 17, 该题直接输出17就好AC代码#include <bits/stdc++.h> using namespace std; int main() { cout << 17; return 0; }B. 启程，通往ACM世界的道路解题思路很容易发现，要赢得比赛，笨娜娜需要赢得的回合数需要超过总回合数的一半。AC代码#include<iostream> using namespace std; int main() { int n; cin >> n; cout << n / 2 + 1; return 0; }C. 最少次数 (简单模拟)解题思路如果该数能被 2 循环整除为 1，统计循环次数并输出。否则输出 -1AC代码#include <bits/stdc++.h> using namespace std; int main() { int n, cnt = 0; cin >> n; while(n % 2 == 0) { n /= 2, ++cnt; } if (n == 1) cout << cnt; else cout << "-1"; return 0; }D.tomori的石头解题思路可以发现，如果 当前位置拥有的石头总数 减去 上一个位置拥有的石头总数 不等于 当前位置所收集的石头数，那么丢失的石头的位置就是当前的位置。#include <bits/stdc++.h> using namespace std; int main() { int n, la = 0, now, temp; cin >> n; for (int i = 0; i < n; ++i) { cin >> temp >> now; if (now - la != temp) { cout << i + 1 << endl; break; } la = now; } return 0; }E.堂吉诃德的骑士之路解题思路暴力循环会超时。手玩一下后,可以发现位置都是一正一负,既 1 -1 2 -2 3 -3 4 -4#include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; if(n > 0) cout << 2 * n - 1 << "\n"; else cout << -2 * n << "\n"; return 0; }H. 画画简单思维题,难度在于三个画布的最优摆放解题思路尽量用完所有的画布空间最优。一个画布 最多画 $2$ 个圆两个画布 最多画 $6$ 个圆三个画布 最多画 $10$ 个圆四个画布 最多画 $15$ 个圆 此时，所有画布的格子都能被用上#include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; int ans = 0; ans += x / 15 * 4; x %= 15; if (x > 10) ans += 4; else if (x > 6) ans += 3; else if (x > 2) ans += 2; else if (x > 0) ans += 1; else ans += 0; cout << ans << " "; } return 0; }G. 值日 (简单模拟)解题思路每次选到要搞卫生的位置时就给该位置打上flag，下次遍历数组时遇到已经打上flag的就跳过AC代码#include <iostream> using namespace std; int a[51]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int n, k, j = 0; cin >> n >> k; for (int i = 1; i <= k; ++i) { int cnt = 0; while (cnt < i) { ++j; if (j > n) j = 1; if (!a[j] && ++cnt == i) break; } a[j] = 1; } cout << j << endl; return 0; }H. GGbond吃棒棒糖解题思路先求出每场比赛使用超级棒棒糖能多获得的分数，然后贪心的从大到小取，如果取到最后GGbond的总分仍无法大于超人强，则输出负一。AC代码#include <bits/stdc++.h> #define LL long long using namespace std; void solve() { int n; LL h, k, hxy = 0; //hxy代码超人强和GGbond的分差 pair<LL, LL> a[100005]; cin >> n >> h >> k; vector<LL> c(n); for (int i = 0; i < n; ++i) { cin >> a[i].first; hxy -= a[i].first; } for(int i = 0; i < n; ++i) { cin >> a[i].second; hxy += a[i].second; c[i] = max(h - a[i].first, a[i].second); } sort(c.rbegin(), c.rend()); if (hxy < 0) { cout << "0\n"; return; } for (int i = 0; i < n; ++i) { hxy -= min(k, c[i]); if (hxy < 0) { cout << i + 1 << endl; return; } } cout << "-1\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); solve(); return 0; }I. A+B problem解题思路按行输出计算结果的每个数字对应每行的字符串AC代码#include<bits/stdc++.h> using namespace std; string str[] = { "##### ....# ##### ##### #...# ##### ##### ##### ##### #####", "#...# ....# ....# ....# #...# #.... #.... ....# #...# #...#", "#...# ....# ....# ....# #...# #.... #.... ....# #...# #...#", "#...# ....# ##### ##### ##### ##### ##### ....# ##### #####", "#...# ....# #.... ....# ....# ....# #...# ....# #...# ....#", "#...# ....# #.... ....# ....# ....# #...# ....# #...# ....#", "##### ....# ##### ##### ....# ##### ##### ....# ##### #####" }; int zz[] = {0, 6, 12, 18, 24, 30, 36, 42, 48, 54}; int main() { int a, b; cin >> a >> b; string num = to_string(a + b); for (auto &i: str) { for (char &j: num) { for (int k = zz[j - '0']; k < zz[j - '0'] + 5; ++k) cout << i[k]; cout << ' '; } cout << endl; } return 0; } J. 笨娜娜的寻宝之路 (二分)解题思路很容易发现，层数对应的总步数就是该层对应矩形的面积，接下来可以二分求出对应步数所在的层数(也可以先预处理出所有的层数情况，并使用 lower_bound 查找)根据奇偶判断从x的正负半轴开始出发，计算最终坐标。AC代码#include <bits/stdc++.h> #define LL long long using namespace std; LL ls[800000], zz = 1, step, layer, x, y; int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); // 预处理层数信息 for (; zz * (2 * zz - 1) < 1e12; ++zz) ls[zz] = zz * (2 * zz - 1); int q; cin >> q; while (q--) { cin >> step; layer = lower_bound(ls, ls + zz, step) - ls; // 二分查找所在层数 step -= ls[layer]; x = layer - 1; if (layer & 1) x = -x; step = abs(step); if (step < layer) y = step; else if (step <= 3 * layer - 3) { y = abs(x); step -= y; if (x < 0) x += step; else x -= step; } else { x = -x; y = layer - (step - (3 * layer - 3) + 1); } cout << x << ' ' << y << endl; } return 0; } https://www.guwolf.com/archives/ZSC-calss-robber.html 2024-01-10T19:29:00+08:00 前言:为避免以后发生 忘记/抢不到课 的情况，于是在愤怒中写下了这个脚本！使用python开发，运行环境基于Python 3.12，其他请自测。经过一个下午的努力(基本在找规律)，已经实现了基本抢课功能，待开发完后在github开源。每日Push代码量:2024-1-10187Require Modules:base64requestjsonurliblxmlfake_useragent开发状态:核心流程功能状态课程列表获取✅选课信息抓取✅提交选课⏳使用try减少fatal错误发生的可能⏳二次验证成功选课⏳附加功能功能开发状态模拟登录(不用自己抓cookie了)✅延迟抢课⏳cookie状态检测⏳cookie失效重登录⏳抢课信息推送⏳课程时间段筛选⏳多线程(感觉没必要)⏳教务系统的登录流程:1.访问首页，服务器下发cookie。(set cookie)2.用户输入完账号密码后，把用户名和密码进行base64编码后拼接，拼接格式为[username(base64)] + %%%(分割) + [password(base64)] 3.携带下发的cookie将数据POST至 https://jwgln.zsc.edu.cn/jsxsd/xk/LoginToXk POST表单encoded=xxx(编码拼接后数据)。选课流程(均需携带经过认证的cookie):1.先向 https://jwgln.zsc.edu.cn/jsxsd/xsxk/xsxk_index?jx0502zbid=[选课列表ID] 发起GET请求，代表你进行该列表的选课。（否则下面会返回404）2.向/jsxsd/xsxkkc/xsxkGgxxkxk?kcxx=&skls=&skxq=&skjc=&sfym=false&sfct=true&szjylb=&sfxx=true发送POST请求获取课程列表，重点是返回的jx02id和jx0404id，下面进行选课提交的时候会用到。相关参数作用kcxx搜索关键词，缺省则返回全部课表sfxx是否屏蔽冲突课程表单数据:sEcho: 1iColumns: 12 (盲猜下面mDataProp个数)sColumns: iDisplayStart: 0iDisplayLength: 15 (猜测一次返回多少个结果)mDataProp_0: kchmDataProp_1: kcmcmDataProp_2: xfmDataProp_3: sklsmDataProp_4: sksjmDataProp_5: skddmDataProp_6: xqmcmDataProp_7: xkrsmDataProp_8: syrsmDataProp_9: ctsmmDataProp_10: szkcflmcmDataProp_11: czOper3.提交选课：请求方式: GET路径: /jsxsd/xsxkkc/ggxxkxkOper需要用到jx0404id和kcid，其他参数未知...示例: https：//[domain]/jsxsd/xsxkkc/ggxxkxkOper?kcid=02114320&cfbs=null&jx0404id=202320242005563&xkzy=&trjf=吐糟篇:1.每访问一个页面就set cookie,还是和上面相同的cookie，导致出现大量重复cookie(不影响脚本)，见下图:2.API出错就返回404状态码，不报原因。3.API返回不符合规范，以及各种奇葩命名4.未知原因的 选课未开放(别人都选完了)。未完待续... https://www.guwolf.com/archives/algo-binary.html 2024-01-04T20:41:00+08:00 什么是二分查找二分查找也叫折半搜索，是用来在一个有序数组中查找某一元素的算法。相较于线性查找,二分查找利用了数组的有序性质,通过调整边界快速缩减查找范围,大大提高了查找效率。线性查找时间复杂度:时间复杂度(最好) O(1)时间复杂度(最坏) O(n)二分查找时间复杂度:时间复杂度(最好) O(1)时间复杂度(最坏) O(logn)1. 整数二分的代码实现以升序数组为例int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (target > arr[mid]) left = mid + 1; else right = mid - 1; } return -1; } STL库里的二分C++ STL库里有两个查找函数std::lower_bound实现了查找首个不小于给定值的元素std::upper_bound实现了查找首个大于给定值的元素二者均采用二分查找，所以使用前应确保数组有序。传入参数first, last -要搜索部分范围的迭代器value -要与元素比较的值返回值指向范围首个符合条件的元素的迭代器，在找不到这种元素时返回last要得到符合条件的元素的下标只需要使用返回迭代器减去first即可比如--- int a[5] = {1,3,5,7,9}; int loc = lower_bound(a, a+5, 3) - a; // loc = 1 int loc = upper_bound(a, a+5, 3) - a; // loc = 2 --- https://www.guwolf.com/archives/algo-sort.html 2024-01-04T19:03:00+08:00 PS:页面右边有该文章的目录，可快捷跳转到对应位置目前该篇只介绍了三种排序算法:冒泡排序、插入排序、快速排序(极度推荐)。以及C++ STL里快排函数sort()的使用。1.冒泡排序1.1 算法介绍时间复杂度(平均) O(n²)时间复杂度(最好) O(n)时间复杂度(最坏) O(n²)空间复杂度 O(1)这应该是世界上知名度最广的一个排序算法了吧(也是时间复杂度最高的算法) ::twemoji:tilted::1.2 代码实现void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { for (int j = 1; j < n - i; ++j) { if (arr[j-1] > arr[j]) swap(arr[j-1], arr[j]); } } } 1.3 GIF原理图2.插入排序2.1 算法介绍时间复杂度(平均) O(n²)时间复杂度(最好) O(n)时间复杂度(最坏) O(n²)空间复杂度 O(1)2.2 代码实现void insertionSort(int arr[], int n) { for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } }2.3 GIF原理图3.快速排序3.1 算法介绍时间复杂度(平均) O(nlogn)时间复杂度(最好) O(nlogn)时间复杂度(最坏) O(n²)空间复杂度 O(nlogn)快速排序采用了分治策略,通过一个pivot(基准值)将数组分成两部分,一部分小于pivot,一部分大于pivot。然后递归对两部分继续排序,直到数组有序。复杂度分析: 最坏情况下,每次pivot都位于边界,会导致递归树退化为链表,时间复杂度为O(n^2)平均情况下,递归树深度为O(logn),每层partition时间为O(n),所以平均时间复杂度为O(nlogn)3.2 代码实现int partition(int arr[], int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; ++j) { if (arr[j] < pivot) { ++i; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[right]); return i + 1; } void quickSort(int arr[], int left, int right) { if (left < right) { int pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); } }3.3 GIF原理图没找到合适的动图，排序过程请看算法介绍4. C++ STL里的排序C++ 标准库里实现了排序的函数std::sort(),印象中其效率是和快排差不多的,该函数定义于头文件 <algorithm>传入参数:参数说明first,last要搜索部分范围的迭代器comp比较函数4.1 对数组进行升序排序sort默认排序顺序是升序#include <iostream> #include <algorithm> using namespace std; int main() { int a[10] = {1,5,9,8,7,5,3,2,6,4}; sort(a, a+10); for (int i = 0; i < 10; ++i) cout << a[i] << ' '; // 1 2 3 4 5 5 6 7 8 9 return 0; } 4.2 对数组进行降序排序这时候就需要自定义比较函数bool compare(int a, int b) { return a > b; } 然后再排序sort(a, a+10, compare); 4.3 对结构体数组进行排序同理自定义排序函数可以让我们对结构体进行排序bool compare(struct aaa A, struct aaa B) { if (A.a == B.a) return A.b > B.b; return A.a > B.a; } 然后再进行排序sort(aaa, aaa+10, compare); 猫猫说 https://www.guwolf.com/archives/API.html 2024-01-04T01:46:00+08:00 这是本站的一个基于公益性质的公共API文档地址:https://api.guwolf.com/备用地址:https://guwolf-api.azurewebsites.net/已实现功能:功能获取IP获取DNS记录待添加功能:功能状态有功能建议请务必通过评论或是其他方式让我得知！！！ヾ(≧∇≦*)ゝ https://www.guwolf.com/archives/End-2023.html 2023-12-31T23:50:00+08:00 还有10分钟就到新的一天，新的一年。本来不想这个时间在写什么文章了，但是仔细一想，我也不需要写什么高谈阔论，什么矫揉造作的文字。感觉2023年并没有发生太多的事情，也没有多大变化。上了大学，只不过是换了个地方继续生活(学习)，进入学校的ACM队，或许是为了更好的追求自己的兴趣，或许也不全是。其他更多的事，不刻意去想，也想不起来有什么了。2024，也许是一个很好的新的开始。过去可能因为过于在乎别人的感受，有些话没有说出来，只能委屈自己，令自己很难受。希望以后在和人交际的时候，不要太看重一些东西，不要太害怕失去一些东西或者说关系，just show myself。只是表达自己的观点，如果认为是正确的话。对于这样的文字，这一年我很少写了，因为我知道的是写的再多，感悟的再深刻，也抵不上不断的在生活中实践来的有用。end. https://www.guwolf.com/archives/poetry-1.html 2023-05-07T18:46:00+08:00 题目：梦断署名：Tan Hao心如夜空月,梦作思绮绮。渺茫相思随风飞,空留余香缕缕。今夜梦中重相逢,重温初见醉花间。梦醒惘然迷离空,明日惆怅空依然。梦中一瞬爱四溢,醒后终是无复别。相思惘然人生路,往梦成云散何时。