QuickSort Dijkstra 3-Way Partitioning

思想

原始的基于 2-Way Partition 的快排在遇到大量重复数据时会退化为 O(n^2),为了解决这个问题,3-Way 快排被提出了。通过将区间分割为“小于”、“等于”和“大于”(基准数)三个部分,获得了趋近 O(nlogn) 的复杂度。不同于 2-Way 快排的是,我们在此选取一个基准数的值,而非一个基准元素。

(小声逼逼:当然为了方便也可以直接改进 2-Way 快排,在每一次基准数归位后遍历全区间元素,将等于基准数的元素交换到基准数旁边,也能获得等价的三个区间。当然,效率相对于 3-Way 快排有所下降,代码实现的复杂度也上升了。)

使用 i 下标表示“小于”区间的上界;使用 q[......]

Read more

自建 vlmcsd KMS 服务器激活 Windows 及 Office 套件

服务端操作

  1. 找一台吃灰小鸡(本地虚拟机也行)
  2. https://github.com/Wind4/vlmcsd/releases 下载 latest release
  3. tar -xzvf binaries.tar.gz 解压
  4. 运行

客户端操作

激活 Windows

各 KMS 激活密钥见 KMS 客户端安装密钥 | Microsoft Docs

  1. 以 Windows 管理员权限运行命令提示符
  2. 指定 kms 批量激活服务器 slmgr /skms [服务器地址]
  3. 执行激活操作 slmgr /ato
  4. 查看有效期 slmgr /xpr

注意:
1. 仅 VOL 批量许可版本的 Windows[……]

Read more

快速排序简易入门

快速排序

快速排序(Quick Sort)因其 O(N\log_{}N) 的复杂度成为最常见的算法之一,甚至被纳入了 C++ 的标准库作为 std::sort 的一部分与插入排序糅合在一起以实现更优的时间复杂度。

在学习快速排序算法之前,让我们首先回顾最经典的排序算法——冒泡排序:经过 (N-1)! 次比较,以 O(N!) 的复杂度完成排序。由于冒泡排序每次只比对相邻的两个元素,所以排序效率相对比较低。

快速排序的优势在于,应用了分治的思想(有点像二分),通过多次迭代将元素依次归位,最终完成排序。单元操作如下:

  1. 最左端 选取端元素作为[……]

Read more

IVHQ 国际志愿者 | 巴厘岛保护海龟项目全纪录(三):融入

Day 1 Mon 文化学习与印尼语

早晨

早晨

一大早便被鸡鸣声唤醒,晨光与虫鸣从窗户涌进来。我所在的宿舍总共居住了四个男生,除一人来自美国以外,剩下三人都是同行校友。

宿舍内

宿舍内

每个床旁边有两个插座,一人一个。考虑到白天在营地时间较少,建议志愿者们除了必备的转接插头以外还要携带一个插线板以给手机、移动电源等电子[……]

Read more