Algorithm

字符串匹配算法总结 KMP虽然经典,但是理解起来极其复杂,好不容易理解好了,便起码来巨麻烦！ 老子就是今天图书馆在写了几个小时才勉强写了一个有bug的、效率不高的KMP,特别是计算next数组的部分。 其实,比KMP算法速度快的算法大把大把,而且理解起来更简单,为何非要抓住KMP呢？笔试出现字符串模式匹配时直接上sunday算法,既简单又高效,何乐而不为？ 说实话,想到sunday算法的那个人,绝对是发散思维,绝对牛。当我在被KMP折磨的够呛的时候,我就琢磨,有没有别的好算法呢？？琢磨了半天也没想出个所以然来。笨啊,脑子不够发散。 下面贴上一位兄弟写的算法总结,很简单 (建议KMP部分就不用看了,看了费脑子) 。 参见: http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html 趁着做Presentation的功夫,顺便做一个总结 字符串匹配: -willamette 在匹配串中寻找模式串是否出现,注意和最长公共子序列相区别(LCS: Longest Common Substring) **-: ** Brute Force(BF或蛮力搜索) **算法: ** 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。 速度最慢。 那么,怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到,Brute Force 是很不intelligent 的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^ 注意,蛮力搜索算法虽然速度慢,但其很通用,文章最后会有一些更多的关于蛮力搜索的信息。 **-: KMP算法 ** 首先介绍的就是KMP 算法。 原始论文: Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977. 这个算法实在是太有名了,大学上的算法课程除了最笨的Brute Force 算法,然后就介绍了KMP 算法。也难怪,呵呵。谁让Knuth D.E. 这么world famous 呢,不仅拿了图灵奖,而且还写出了计算机界的Bible 《The Art of Computer Programming》( 业内人士一般简称TAOCP). 稍稍提一下,有个叫H.A.Simon 的家伙,不仅拿了Turing Award ,顺手拿了个Nobel Economics Award ,做了AI 的爸爸,还是Chicago Univ 的Politics PhD ,可谓全才。 ...

本文整理一般二叉树、二叉搜索树（BST）与平衡树的概念；BST 的插入、查找、删除与中序遍历的 Go 实现见我的 leetcode 仓库 下的 tree/（bst.go、bst_test.go）。 二叉树 (Binary Tree) 二叉树 (Binary Tree) 是包含 n 个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。 二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。 graph TD n1((1)) n2((2)) n3((3)) n4((4)) n5((5)) n7((7)) n10((10)) n11((11)) n14((14)) n1 --> n2 n1 --> n3 n2 --> n4 n2 --> n5 n3 --> n7 n5 --> n10 n5 --> n11 n7 --> n14 满二叉树 Full Binary Tree 对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。 graph TD n1((1)) n2((2)) n3((3)) n4((4)) n5((5)) n6((6)) n7((7)) n8((8)) n9((9)) n10((10)) n11((11)) n12((12)) n13((13)) n14((14)) n15((15)) n1 --> n2 n1 --> n3 n2 --> n4 n2 --> n5 n3 --> n6 n3 --> n7 n4 --> n8 n4 --> n9 n5 --> n10 n5 --> n11 n6 --> n12 n6 --> n13 n7 --> n14 n7 --> n15 完全二叉树 Complete Binary Tree 对于一棵具有 n 个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为 i 的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。 ...

二叉搜索树 红黑树本质上就是一棵二叉搜索树（Binary Search Tree, BST）。BST 的定义、性质与退化成链表后性能变差的问题，见 二叉树与二叉搜索树 §二叉搜索树 Binary Search Tree。 红黑树的性质 红黑树在二叉搜索树的基础上增加了着色和相关的性质，使得树相对平衡，从而保证查找、插入、删除的时间复杂度最坏为 O(log n)。要保证一棵有 n 个结点的红黑树的高度始终保持在 O(log n)，需要满足以下 5 条性质： 每个结点要么是红色，要么是黑色。 根结点是黑色。 每个叶结点（即树尾端的 NIL 指针或 NULL 结点）是黑色。 如果一个结点是红色，那么它的两个子结点都是黑色。 对于任一结点，其到叶结点的每一条路径都包含相同数目的黑色结点。 正是这 5 条性质，使得一棵有 n 个结点的红黑树始终保持 O(log n) 的高度，从而解释了上面"查找、插入、删除的时间复杂度最坏为 O(log n)“这一结论的原因。 示例：一棵合法的红黑树 下面几张图都用同一套配色：红色底色代表红色节点，深色底色代表黑色节点（NIL 叶子也按黑色处理）；后面删除修复的例子里还会多一种"双重黑"的颜色，专门标出来。 graph TD classDef red fill:#d64545,stroke:#333,color:#fff; classDef black fill:#2c2c2c,stroke:#333,color:#fff; r((10)):::black a((5)):::red b((3)):::black c((7)):::black d((15)):::black e[NIL]:::black f((20)):::red r --> a r --> d a --> b a --> c d --> e d --> f 对照上面的 5 条性质检查这棵树：根 10 是黑色；红色节点 5、20 的子节点都是黑色（5 的子节点 3、7 是黑色，20 的两个子节点是图中未画出的 NIL，同样按黑色计）；从根到任意一条路径上的黑色节点数都是 3（例如 10 → 5 → 3 → NIL 与 10 → 15 → 20 → NIL 都是 3 个黑色节点），满足黑高一致。 ...

AVL 树是最早出现的自平衡二叉搜索树，由 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年在论文《An algorithm for the organization of information》中提出，因此得名 AVL（发明者姓氏首字母），也叫高度平衡树。 平衡二叉树的通用定义（平衡因子、失衡、单旋恢复平衡的例子）见 二叉树与二叉搜索树 §平衡二叉树 Balanced Binary Tree，本文只讲 AVL 特有的部分：严格平衡条件、四种失衡情况的旋转、插入删除的复杂度，以及和其他平衡树、常见平衡树家族的关系。 严格平衡条件 一棵 AVL 树满足以下条件（递归定义）： 左子树和右子树都是 AVL 树。 左子树和右子树的高度差不超过 1。 相比红黑树用颜色规则换取的"相对平衡"，AVL 树是严格平衡：任意结点的平衡因子（左子树高度 − 右子树高度）只能取 -1、0、1。这带来的好处是查找效率稳定，代价是插入、删除时更容易触发再平衡。 树高的维护 判断是否失衡需要知道每个结点的子树高度，通常在结点里额外记一个 height 字段： 空结点（NIL）的高度记为 -1 叶子结点的高度为 0 非叶子结点的高度 = max(左子树高度, 右子树高度) + 1 插入或删除一个结点后，从该结点沿父指针回溯到根，逐层重新计算高度；一旦某个祖先的平衡因子超出 [-1, 1]，该结点就是失衡点，需要旋转恢复平衡。 失衡的四种情况与旋转 失衡点的位置只有 4 种可能，分别对应不同的旋转方式： 情况 触发位置 旋转方式 LL（左左） 左子树的左子树过高 对失衡点做一次右旋 RR（右右） 右子树的右子树过高 对失衡点做一次左旋 LR（左右） 左子树的右子树过高 先对左子树左旋，再对失衡点右旋（双旋） RL（右左） 右子树的左子树过高 先对右子树右旋，再对失衡点左旋（双旋） RR 单旋的完整示例见 二叉树与二叉搜索树 §插入示例，LL 是它的镜像。下面补充一个 LR 双旋的例子。 ...

一句话 DAG = Directed Acyclic Graph，中文常叫有向无环图。它是一种图：边有方向，且沿着方向走永远走不回起点。 先说「图」 图（Graph）由两类东西组成： 节点（Node / Vertex）：事物本身，比如「编译模块 A」「跑测试」「部署」 边（Edge）：节点之间的关系，比如「A 完成后才能做 B」 边如果没有方向（A—B 和 B—A 一样），叫无向图；边有方向（A → B 表示从 A 到 B），叫有向图（Directed Graph）。 Directed：边有方向 在任务依赖、数据流水线里，方向通常表示「先后」或「依赖」： 写接口 ──► 写单测 ──► 跑 pytest 意思是：写接口完成之后才能写单测；单测就绪之后才能跑 pytest。反过来走没有意义——不能「先跑 pytest 再写接口」。 Acyclic：不能有环 「无环」是说：沿着箭头走，不会绕回已经走过的节点。 有环的例子（这不是 DAG）： A ──► B ▲ │ └─────┘ A 等 B，B 又等 A，两边永远等不到对方。包管理里的循环依赖、构建系统里的互相引用，本质都是环带来的死锁。 无环的例子（这是 DAG）： ┌──► B ──► D A ───┤ └──► C ──► E 从 A 出发可以走到 B、C、D、E，但没有任何一条路径能回到 A。因此一定存在至少一个「没有入边的起点」，以及至少一个「没有出边的终点」。 ...

Xorshift 是什么 Xorshift 是 George Marsaglia 在 2003 年发表的一类伪随机数生成算法（PRNG，Pseudo-Random Number Generator），核心思路是反复对一个整数状态做"自己和自己移位后的版本"做异或（XOR），只用异或和移位两种运算就能生成看起来随机的数字序列。 它属于线性反馈移位寄存器（LFSR，Linear Feedback Shift Register）的一种变体，相比传统的线性同余法（LCG，Linear Congruential Generator，也就是很多语言标准库 rand() 背后的算法）不需要乘法和取模，只用位运算，速度快很多；相比更复杂的 Mersenne Twister（java.util.Random 用的不是这个，但 Python、PHP 等语言的默认随机数用的是它），实现更简单、状态更小。 代价是随机质量不如 Mersenne Twister，不能用于密码学场景（不是 CSPRNG，Cryptographically Secure PRNG），但对哈希表、游戏、模拟、需要"看起来随机就行"的场景完全够用，且速度优势明显。 基本算法 最经典的 32 位 xorshift 只需要一个非零的整数状态 x 和三次移位异或： uint32_t xorshift32(uint32_t x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; } 每次调用把上一次的输出作为下一次的输入（状态），就能生成一串伪随机序列。三个移位量 (13, 17, 5) 不是随便选的——Marsaglia 在论文里给出了一批能保证生成的序列覆盖 2^32 - 1 个非零状态（即最大周期）的移位量组合，(13, 17, 5) 是其中常用的一组。如果移位量选得不好，会导致序列过早循环或者分布不均匀。 64 位状态的版本同理，只是移位量不同： uint64_t xorshift64(uint64_t x) { x ^= x << 13; x ^= x >> 7; x ^= x << 17; return x; } 为什么异或和移位比乘除法快 xorshift 只用异或和移位，LCG 需要乘法，还常常需要取模——这两类操作在 CPU 上的实际开销差距很大，不只是"位运算听起来更底层"这种直觉。 ...

LCG 是什么 线性同余生成器（LCG，Linear Congruential Generator）是历史最悠久、实现最简单的一类伪随机数算法（PRNG，Pseudo-Random Number Generator）。1949 年由 D. H. Lehmer 提出雏形，此后几十年里几乎所有编程语言标准库的 rand() 都是它的某个变体。 它的核心是一条递推公式：给定当前状态 seed，用一次乘法、一次加法、一次取模算出下一个状态，同时把这个状态作为输出。相比 Mersenne Twister 随机数算法 和 Xorshift 伪随机数算法，LCG 实现最简单、状态最小，但随机质量也最差，且不是密码学安全的随机数生成器（不是 CSPRNG，Cryptographically Secure PRNG），不能用在密钥生成、令牌生成等安全场景。 递推公式 X(n+1) = (a * X(n) + c) mod m 四个参数决定了一个具体的 LCG： X(0)：种子（seed），初始状态 a：乘数（multiplier） c：增量（increment） m：模数（modulus） c = 0 的特例叫乘同余生成器（multiplicative congruential generator，也叫 Lehmer RNG）；c != 0 时才是完整的（mixed）LCG。取模运算保证了状态永远落在 [0, m) 区间内，序列迟早会回到某个之前出现过的状态并开始循环——这个循环长度就是"周期"，LCG 的周期上限是 m。 参数怎么选：Hull–Dobell 定理 不是随便选四个数字就能得到一个"好"的 LCG。如果参数选得不好，序列可能远没跑到 m 就开始循环，或者呈现明显的规律。Hull–Dobell 定理给出了 c != 0 时序列能达到最大周期 m（即遍历 [0, m) 里所有整数才循环）的充要条件： ...

Mersenne Twister 是什么 Mersenne Twister（简称 MT，梅森旋转算法）是松本真（Makoto Matsumoto）和西村拓士（Takuji Nishimura）在 1997 年发表的伪随机数生成算法（PRNG），名字来自它的周期长度——最常用的变体 MT19937 的周期是 2^19937 - 1，这是一个梅森素数（Mersenne prime，形如 2^p - 1 的素数）。 它是目前应用最广泛的通用 PRNG 之一：Python、PHP、R、Ruby、Excel 的默认随机数生成器用的都是 MT19937；C++11 标准库 <random> 里的 std::mt19937 也是它。相比 Xorshift 伪随机数算法 和 Java Random 随机数 里的线性同余法（LCG），MT 的随机质量（统计意义上的均匀性、独立性）好得多，周期也长得多，代价是内部状态更大、实现更复杂。 和 xorshift、LCG 一样，MT 不是密码学安全的随机数生成器（不是 CSPRNG）：观察连续 624 个输出就能反推出完整的内部状态，从而预测后续所有输出，所以不能用在密钥生成、令牌生成等安全场景，这些场景要用专门的 CSPRNG（比如 Java 的 java.security.SecureRandom）。 核心设计 状态：624 个 32 位整数 MT19937 的内部状态是一个长度 624 的 32 位整数数组，一共 624 * 32 = 19968 位，比 xorshift（几十到几百位状态）或 LCG（48 位状态）大得多——这也是"随机质量更好"的代价之一：状态越大，能表达的不同序列就越多，越不容易在短序列内暴露周期性规律。 生成流程分两步 状态推进（twist）：每消耗完 624 个输出后，对整个状态数组做一次"扭转"变换，生成下一批 624 个新状态。扭转的核心是对相邻状态做位组合，再乘上一个固定的常数矩阵（用移位和异或实现，不是真正的矩阵乘法，效果类似线性反馈移位寄存器）。 输出提炼（tempering）：每次取值时，不直接返回状态数组里的原始整数，而是先对它做一轮固定的移位、掩码、异或组合（tempering），目的是消除原始状态里明显的统计规律，让直接输出的比特看起来更均匀。 这种"大状态 + 定期批量刷新 + 每次输出前额外处理"的设计，是 MT 和 xorshift/LCG 这类"每次输出就是一次状态更新"的算法的主要区别。 ...

Swiss Table 是什么 Swiss Table 是 Google 在 2017 年前后公开的一种高性能哈希表设计（最早用在 Abseil 库的 absl::flat_hash_map 里），本质上是开放地址法的一个工程变体：在经典的线性探测 / 二次探测之上，加入了按"组"批量比较的机制，充分利用 CPU 的 SIMD 指令与缓存局部性。基本的开链法、开放地址法概念见 开链法与开放地址法。 它已经被多个主流项目采纳：Rust 的 hashbrown（std::collections::HashMap 自 1.36 起的底层实现）就是 Google SwissTable 的 Rust 移植版；Go 1.24 内置的 map 也从桶+溢出桶的实现换成了基于 Swiss Table 思路的新实现（细节见 开链法与开放地址法#在-go-语言中的应用）。 核心设计 控制字节（control byte） Swiss Table 给每个槽位（slot）配一个额外的 1 字节"控制字节"，不存实际数据，只存槽位的状态和一段哈希指纹： 槽位状态：EMPTY（从未用过）、DELETED（曾经用过、已删除，即墓碑标记）、FULL（当前有效数据）。 如果槽位是 FULL，控制字节里还会存一段哈希指纹，Abseil 里称为 h2，取的是 key 完整哈希值的低 7 位。 h1 和 h2：哈希值一分为二 Swiss Table 把 key 的哈希值拆成两部分： h1：哈希值的剩余高位，用来计算这个 key 应该落在哪一个"组"（group），即决定探测起点，作用类似前文开放地址法里的 root = hash(key) % m。 h2：哈希值的低 7 位，存进控制字节，作为一个廉价的"预筛选"指纹。 分组批量比较 控制字节在内存中是连续排列的，按组打包（Abseil/hashbrown 里一组 16 个，Go 1.24 里一组 8 个，打包进一个 64 位控制字）。查找时： ...

开链法与开放地址法，Separate Chaining and Open Addressing 哈希表在插入元素时，如果两个不同的 key 计算出的哈希值落到了数组的同一个位置，就发生了哈希冲突（hash collision）。解决哈希冲突主要有两种思路：开链法（Separate Chaining）和开放地址法（Open Addressing）。Java 的 HashMap 用的是开链法；Python 的 dict 用的是开放地址法。Java 里也有用开放地址法的例子，比如 IdentityHashMap 和 ThreadLocal.ThreadLocalMap，详见后文「在 Java 中的应用」一节。 开链法，Separate Chaining 开链法是一种二维结构：第一维是一个数组，数组的每个槽位（bucket）挂着一个链表（第二维）。插入元素时，先用 hash 函数算出该 key 应该落在数组的哪个槽位，然后直接把这个 key（连同 value）作为一个节点追加到该槽位的链表上。 当多个不同的 key 计算出相同的槽位时，它们并不会互相覆盖或者被挪到别处，而是全部挂在同一个槽位的链表里，按顺序排列。查找时，先定位到槽位，然后遍历该槽位的链表，逐个比较 key 是否相等，直到找到目标或者遍历到链表末尾。 优点 实现简单，冲突处理直观，槽位之间互不影响。 删除操作非常简单，只需要从链表中把对应节点摘除即可，不会影响其它元素的查找路径。 负载因子（元素个数 / 数组长度）可以大于 1，只是链表会变长，查找退化为线性扫描。 负载因子，Load Factor 负载因子的英文是 load factor，公式为 load factor = 哈希表中总元素个数 / 数组长度（槽位数）。这里的"元素个数"指的是整个哈希表中的元素总数，而不是某一个槽位对应的元素个数；某个槽位挂了多少个元素（链表长度）反映的是 hash 分布是否均匀，是另一个维度的问题。例如数组长度为 16，哈希表中一共存了 12 个元素，此时 load factor 就是 0.75。 开链法下即使 load factor 大于 1（元素个数超过数组长度）也不会出错，只是链表会变长；而开放地址法由于只有一个数组，load factor 不能超过 1（数组会满）。 ...

大 O 表示法（Big O Notation） 大 O 符号用来描述算法的时间复杂度：输入规模增长时，算法运行时间的增长趋势。 最直观的两种复杂度是： O(1)：一次操作即可直接取得目标元素，例如字典（哈希表）的查找 O(n)：需要逐一检查 n 个元素才能找到目标，例如遍历数组查找 那么 O(log n) 是什么意思？ O(log n) 的由来：二分查找 O(log n) 最常见的例子是二分查找。二分查找最好情况下复杂度是 O(1)（第一次就命中中间元素），最坏情况下是 O(log n)。下面从最坏情况推导这个结论。 假设有 16 个元素的有序数组，要查找的目标值小于数组中间的元素。每比较一次中间元素，搜索范围就减半： 16 个元素 → 取中间元素比较，目标在前一半 → 剩余 8 个元素 8 个元素 → 剩余 4 个元素 4 个元素 → 剩余 2 个元素 2 个元素 → 剩余 1 个元素，查找结束 也就是说，从 16 个元素中定位目标，最多需要将数组对半分割 4 次： $$ \frac{16}{2^4} = 1 $$推广到 n 个元素，设需要分割 k 次才能剩下 1 个元素： ...

Hash 表也称散列表，也有直接译作哈希表，是一种特殊的数据结构，同数组、链表以及二叉排序树等相比较有很明显的区别：它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。这源于 Hash 表设计的特殊性，它采用函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。 java.util.Hashtable 是 Java 中最早的哈希表实现，自 JDK 1.0（1996 年）就已存在。在现代 Java 中它依然保留，但仅用于向后兼容旧代码：非线程安全场景推荐使用 HashMap，需要线程安全时推荐使用 ConcurrentHashMap，两者性能和易用性都更好，Hashtable 已不建议在新代码中使用。 Hash 表的设计思想 对于一般的线性表，比如链表，如果要存储联系人信息： 张三 13980593357 李四 15828662334 王五 13409821234 张帅 13890583472 可能会设计一个结构体包含姓名、手机号码这些信息，然后把 4 个联系人的信息存到一张链表中。当要查找“李四 15828662334”这条记录是否在这张链表中，或者想要得到李四的手机号码时，可能会从链表的头结点开始遍历，依次将每个结点中的姓名同“李四”进行比较，直到查找成功或者失败为止，这种做法的时间复杂度为 O(n)。即使采用二叉排序树进行存储，也最多为 O(logn)。假设能够通过“李四”这个信息直接获取到该记录在表中的存储位置，就能省掉中间关键字比较的这个环节，复杂度直接降到 O(1)。Hash 表就能够达到这样的效果。 Hash 表采用一个映射函数 f : key -> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置。通常情况下，这种映射关系称作 Hash 函数，而通过 Hash 函数和关键字计算出来的存储位置（注意这里的存储位置只是表中的存储位置，并不是实际的物理地址）称作 Hash 地址。比如上述例子中，假如联系人信息采用 Hash 表存储，则当想要找到“李四”的信息时，直接根据“李四”和 Hash 函数计算出 Hash 地址即可。 hashCode 与 equals 的关系 有人会说，可以直接根据 hashCode 值判断两个对象是否相等吗？肯定是不可以的，因为不同的对象可能会生成相同的 hashCode 值。虽然不能根据 hashCode 值判断两个对象是否相等，但是可以直接根据 hashCode 值判断两个对象不等——如果两个对象的 hashCode 值不等，则必定是两个不同的对象。如果要判断两个对象是否真正相等，必须通过 equals 方法。 ...

常见排序算法： 冒泡排序 选择排序 插入排序 希尔排序 快速排序 归并排序 堆排序 计数排序 桶排序 基数排序 推荐学习顺序： 冒泡 → 选择 → 插入 → 快速 → 归并 → 堆 冒泡排序 Bubble Sort 相邻元素两两比较，大的往后"冒泡"，每轮将最大值沉到末尾。 时间复杂度：O(n²) 空间复杂度：O(1) 稳定排序 def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr # 测试 arr = [64, 34, 25, 12, 22, 11, 90] print("排序前:", arr) bubble_sort(arr) print("排序后:", arr) 执行过程（以 [5, 3, 1] 为例）： 第1轮： j=0: 5 > 3，交换 → [3, 5, 1] j=1: 5 > 1，交换 → [3, 1, 5] ← 最大值 5 沉底 第2轮： j=0: 3 > 1，交换 → [1, 3, 5] ← 次大值 3 到位 第3轮：只剩1个，已有序 外层 i 控制轮数，每轮确定一个最大值的位置 内层 n - i - 1 让已排好的尾部不再参与比较 a, b = b, a 是 Python 交换变量的惯用写法 选择排序 Selection Sort 每轮从未排序部分找最小值，放到已排序部分的末尾。 ...

抽奖概率-三种算法 http://www.cnblogs.com/younggun/p/3249772.html 一、逢"几"中奖 逢"几"中奖,即通过预估抽奖人数和奖品数来判断,“几”=(抽奖人数/奖品数)*N。这是一种最简单抽奖算法,适合抽奖人数众多,而且互相无联系的情况。如今大为流行的微博转发得奖就常常使用这种算法,即根据转发次数来决定奖品归属,透明而且具有激励性。 当然这个"几"也不单只次数,还可能是时间,逢某个时间点就可以抽中,不过这种方案可能产生无人中奖和很多人中奖的情况,时间点的安排很关键！这个时间点一旦公布出去,那就是秒杀,霍霍。。 逢"几"中奖有很多弊端,但是非常简单,很容易实现,被很多抽奖活动所采用,有些会公布抽奖规则,激励抽奖,有些则不会公布,其实后台运行的可能也是这个算法,简单高效又不失公平。在信息不透明的情况下,鬼知道你是第几个抽奖的,哈哈。。 二、概率抽奖 所谓概率抽奖是最容易想到的抽奖算法了,这个概率可以是一成不变的,也可以是一直在变化调整的,最难的是采用多大的概率,何种情况下采用何种概率。这个也没有什么通用的方案,不同的应用场景,所用的概率算法不同。下面介绍一种算法,根据奖品的过期日期来计算它当前时间的中奖率,当时间逐渐接近奖品过期时间时,中奖概率会逐渐发生变化,如果设为1表示线性衰减,2为平方衰减,以此类推。 importjava.util.Date; importjava.util.Random; publicclass LotteryTool { private double factor; private double probability; private Random rand; private LotteryTool(double probability, long expireTime, int reduce){ this.factor = (double) System.currentTimeMillis() / expireTime; this.probability = probability * Math.pow(factor, reduce); this.rand = new Random(System.currentTimeMillis()); } public static LotteryTool getInstance(double probability, longexpireTime, int reduce) { return new LotteryTool(probability, expireTime, reduce); } public boolean isLucky(long expected) { long token = generateLong(); expected = expected % (int) (1 / probability); ...