游戏引擎学习第232天
分享昨天聊天中提到的链接有一位网友分享了一个 MIT OpenCourseWare 的公开课视频链接，我们在推特上转发了谁人视频。团体来说，那是一场非常不错的讲座。虽然有些部分听起来照旧比力晦涩，但它确实澄清了我们对 “P 与 NP 题目” 的不少疑惑。比如，为什么人们在谈论这些概念时常常说出一些似是而非的说法，甚至会出现看似互相矛盾的说法，让人感到困惑，不知道到底该怎么明白。
虽然我们平常不会在这个系列中深入讨论 P 和 NP 这类理论计算机科学的题目，因为这并不是我们认识或重点教学的内容，但偶然提到这些内容作为旁注照旧很有意义的。我们渴望通过这些分享，能够引发大家去主动了解和探索这些领域。
所以我们想扼要地提一提谁人视频里说了些什么，渴望能引起一些朋侪的兴趣。那是 MIT 的一门开放课程，不仅可以看那一节课的视频，还可以顺着去看更多相关内容，深入学习理论计算机科学的知识。
虽然这些内容不属于我们这个项目的重要范围，也不是我们所擅长的部分，但它们无疑是非常有代价的知识。渴望大家有机会能去看看，拓展一下视野，也许会对算法、计算复杂性甚至日后的体系设计带来新的明白。
黑板：题目“难度”品级划分
我们今天整理并总结了一次关于计算复杂度理论中 P、NP、NP-hard、NP-complete 等概念的教学和明白过程，下面是详细的中文总结：
我们先从一个非常直观的图开始明白。想象有一条从“容易”到“困难”的线，表示题目的难度渐渐增加。我们不严格用“复杂度”这个术语，而只是笼统地说“困难程度”——越往右题目越难，越往左越简单。
1. 各类复杂度类的范围划分：
[*]P：是最先被框定的区间，表示“多项式时间可解的题目”，这些是计算机可以在合理时间内解决的题目。
[*]NP：则是一个包含P的更大集合。即，所有P中的题目也属于NP，但NP中还可能包含一些我们不知道是否可以在多项式时间内解决的题目。NP指的是“非确定性多项式时间”，意指这些题目的解可以在多项式时间内验证，但未必能在多项式时间内找到。
[*]EXP（Exponential Time）：表示需要指数时间才气解决的题目，即雷同 2 n 2^n 2n 级别复杂度的题目，远远比P和NP中题目困难。
[*]R（Recursive）：是所有可以在有限时间内解决的题目（哪怕是天文数字的时间），只要最终可以解出来，就属于R。
[*]不可计算题目：比如“停机题目”，甚至不属于R，这些题目无法在任何有限时间内解出，是图最右边甚至在图外的东西。
2. NP 是 P 的超集
这一点非常关键：NP是P的超集。P ⊆ NP。这意味着：
[*]如果一个题目属于P，那么它肯定也属于NP。
[*]但如果一个题目属于NP，并不意味着它属于P。
换句话说，在我们还不知道P与NP是否相当的条件下，NP中可能存在严格比P更难的题目，但也可能不存在。这就是闻名的“P vs NP”题目。
3. NP-hard 的真正含义
许多人对“NP-hard”这个术语有误解。我们本以为“NP-hard”意味着某个题目不在NP中，即比NP还难。但现实上，术语“hard”在这里是表示“大于等于NP的难度”，也就是说：
一个 NP-hard 的题目要么与NP中最难的题目一样难，要么比它们还难。
它可以是NP内的最难题目（也可能在NP之外）。因此，“NP-hard”不清除题目位于NP之中，它只是指这个题目至少和NP中最难的题目一样困难。
4. NP-complete 的精确界说
这个术语经常被混淆，其实它的界说非常精确：
NP-complete 的题目是那些既属于NP，又是NP-hard的题目。
换句话说：
[*]它必须在NP中（可以在多项式时间内验证解）。
[*]它必须是NP中最困难的题目之一（所有NP题目都能归约到它上面）。
因此，NP-complete 是 NP 类中最核心的一类题目。如果有一个 NP-complete 题目被证实可以在多项式时间内解决，那就等于所有 NP 题目都可以在多项式时间内解决，即 P = NP。
如果一个题目在NP中但没有被证实是NP-hard，它就不是NP-complete，只是一个平凡的NP题目。NP-complete 的题目处于整个NP集合的“最右端”，是NP中最难的题目。
5. NP与EXP之间是否存在空档？
我们目前并不清晰 NP 与 EXP 之间是否真的存在一个“中心地带”。也就是说：
[*]可能存在一些题目属于 EXP，但不属于 NP。
[*]也可能某天被证实所有 EXP 中的现实题目也都在 NP 中（尽管这不太可能）。
同理，连 P 和 NP 是不是相当，我们都还无法确定。我们只是推测 P ≠ NP，但目前没有确凿证据。
6. 超出R的不可解题目
我们还提到了一些连在有限时间内都无法解决的题目。例如“停机题目”（Halting Problem）就不属于R类。也就是说，没有一个算法可以判定任意步调是否会停机，它是一个真正不可解的题目。
总结关键点：
[*]P 是可以在多项式时间内解决的题目。
[*]NP 是可以在多项式时间内验证解的题目，包含P。
[*]NP-hard 是至少和NP中最难题目一样难的题目。
[*]NP-complete 是既属于NP又是NP-hard的“最难的NP题目”。
[*]EXP 是需要指数时间的题目，远比P和NP难。
[*]R 是所有有限时间内能解的题目。
[*]有些题目甚至不属于R，比如停机题目，是无法在有限时间内解答的题目。
这个结构图像极大地帮助我们理清了各种复杂度类之间的包含与关系，明确了各种术语的含义，并提供了一种在面对这些概念时不再混淆的直观方式。对于非理论计算机科学出身的人来说，这种方式尤其友好，非常值得推荐给有兴趣了解复杂度基础的朋侪。
黑板：观光商题目（TSP）先容
观光商题目（Travelling Salesman Problem，简称 TSP）是计算机科学和运筹学中一个非常闻名的经典组合优化题目，经常被用来说明算法设计、复杂度理论和人工智能等领域中的关键概念。
题目描述：
假设有一个“观光贩子”，他要访问若干个城市，每个城市只能访问一次，末了回到出发城市。每两个城市之间的距离（或代价）是已知的。请找出一条总距离最短的路径，使得贩子能够访问所有城市并回到出发点。
举个简单的例子：
假设有4个城市：A、B、C、D，它们之间的距离如下：
ABCDA-527B5-43C24-6D736- 我们要找的就是一条路径，比如：
A → C → B → D → A，总距离是 2 + 4 + 3 + 7 = 16
但也许有一条更短的路径？这就是我们要找的最优解。
我们在明白观光商题目（Traveling Salesman Problem, 简称 TSP）和NP题目之间的关系时，碰到了一些概念上的困惑和细节需要厘清。
起首，需要明白“NP题目”在计算机科学理论中的界说。NP题目严格指的是“决策题目”（decision problem），即只能返回“是”或“否”的布尔值题目。之所以限定为布尔值，是因为NP类题目的一个核心特性是：一旦有了解答，我们可以在多项式时间内验证该解是否正确。而不是说题目自己一定要返回一个最优路径或复杂结构。也就是说，NP题目并不关心如何找到解，而是关注一旦有人提供了解，是否可以快速验证这个解是否满足要求。
观光商题目自己是一个最优化题目，要求我们找出一条遍历所有节点、并且路径总长度最短的路径，这显然无法直接返回布尔值结果。因此，为了把它转化成决策题目情势，我们可以如许改写它：“是否存在一条遍历所有节点、总路径长度小于某个给定值K的路径？” 这个题目的答案就是一个“是”或“否”，可以符合NP的界说。
如许转换以后，我们就能够使用NP理论来分析它。因为当别人告诉我们有如许一条路径时，我们可以用多项式时间验证它是否满足长度小于K，并遍历了所有节点。也就是说，虽然原始TSP是一个最优化题目，但其决策版本是可以归入NP的。
接下来是重点：有人提出一个思路，说如果有办法解决这个决策版本，那么就可以使用“二分搜索”（binary search）的方法反复调用这个决策题目，来逼近原始题目的最优解。比如我们可以不停尝试不同的K值，询问“是否存在长度小于K的路径”，逐步缩小范围，从而找出最短路径的长度。
但是这个思路存在疑点。一个关键题目是：在进行二分搜索的时候，我们需要知道路径长度的上下限。而路径的长度是由图中每条边的“权重”或“本钱”决定的，而这些本钱是可以被任意设置的。比如，如果图中的边权都设置得非常大（比如边长是 2 的 2 的 n 次方），那么纵然用二分法，每次比力K值时也要处置惩罚一个非常大的数，如许会导致我们必须进行非常多次的迭代。
进一步说，即便假设我们统共进行了 log(M) 次询问（M 是路径最大可能总长度），但如果 M 是一个指数级的值，比如 2(2n)，那么 log(M) 就是 2^n，这是一个指数级的复杂度。这意味着，虽然我们每次调用决策函数的本钱可能是多项式的，但整个二分搜索过程的总本钱依然是指数级的。
所以题目的核心在于：图中的边权是输入的一部分，而它们的最大值直接影响了我们是否能用多项式时间完成这项工作。如果边权可以被任意设定为巨大的数值，那么这个所谓的“二分搜索解法”就不再是一个多项式时间的算法，而可能会退化为指数时间。
因此，有人提出的观点是：纵然P=NP，也不意味着我们就可以在多项式时间内解决真正的观光商题目（即最优化版本）。决策版本可以归入NP，并在理论上满足P=NP时的可解性；但现实优化题目依赖于路径长度的具体数值，而这些路径长度可以轻易地被设置为使算法变慢。
结论是，纵然从理论角度看TSP的决策版在NP内，并可能在P=NP的条件下被解决，但真正的最优化TSP题目是否也因此变得可解，仍然有待澄清。特别是要处置惩罚路径权庞大小对算法运行时间的影响，这一点目前的表明还不够令人信服。因此，在未看到一个完整的、可以处置惩罚任意路径长度的多项式算法之前，我们不能断言TSP在P=NP时就必然能在P时间内求解。
如今回到我们正在处置惩罚的排序话题和更现实的题目上来。我们之条件到过，之所以不认识那么多计算机科学理论，是因为在现实工作中很少真正碰到这些理论需要直策应用的场景，因此也就没有太强的动力去深入学习这些内容。
但这并不意味着所有CS理论知识都无用。我们始终认为，大O符号（Big-O notation）这类表示算法复杂度的工具，是非常有用且实用的。我们在日常编程中经常用到它，比如当我们在写某段代码时，脑海中就会天然地浮现“这段可能是O(n²)”的判定，这种判定帮助我们快速评估算法的可扩展性和性能瓶颈。能够拥有这种抽象能力，是因为有理论工作者们事先为我们创建了这些分析框架，对此我们是非常感激的。
昨天我们还在Twitter上和Tom Forsythe交流了一下，他原本以为我们会诉苦这些理论没用，结果我们并不这么认为。虽然我们爱诉苦、爱吐槽各种东西，但排序复杂度和大O符号这种基础理论，确实是我们不停认为非常有用的工具，不在我们吐槽的范围之内。
当然，其他更复杂的理论，比如NP、图论、复杂性阶层等等，我们的了解比力浮浅，而且从未真正碰到过需要用它们解决的题目，所以也说不上它们是否有现实作用。但就像许多数学知识一样，当真正深入把握之后，才可能意识到它们的用武之地。如果不学透，当然很难在实战中运用。
因此我们认为，那些理论目前看似“没用”，并不代表它们永久没有用，关键是看什么时候真正需要它们。一旦明白深入，也许就能发现它们的代价。正因如此，纵然目前用不到，我们也乐意以好奇心去探索这些知识。
好了，回到我们的排序主题——这是个更贴近现实应用的题目，下面继续讨论。
黑板：排序相关内容
昨天我们简单提到过，冒泡排序的时间复杂度是 O ( n 2 ) O(n^2) O(n2)。我们之所以得出这个结论，是因为在排序过程中需要对元素进行多次遍历。假设我们要排序的元素有 n n n 个，那么整个排序过程大致会进行 n n n 次完整的遍历。
每一轮遍历中，需要对所有的元素进行比力，而每一次比力的单位操作自己数量也是 n n n 级别的。因此，整个过程就是 n n n 次遍历乘以每次 n n n 个比力操作，总体时间复杂度就是 n × n = n 2 n \times n = n^2 n×n=n2，也就是我们说的 O ( n 2 ) O(n^2) O(n2)。
这个推理非常直观，从代码中也能清晰地看出来。虽然当前没有展示代码，但在前面讨论中已经提到过，在具体实现冒泡排序时，外层是一个循环，控制着每一次“冒泡”的过程，而内层则是一个逐元素的比力与互换。如许嵌套的双层循环自己就体现了 n 2 n^2 n2 的性子。
如许的复杂度分析很有现实代价，它可以帮助我们在编写算法时，快速评估其在大数据量场景下的性能表现，判定是否需要更高效的算法替代现有方案。这种思维方式在许多编程场景中都非常常见和重要。
game_render_group.cpp：当前 SortEntries 函数的时间复杂度是 O(n²)
我们在这里现实看到了排序的代码结构，非常直观地展示了排序的复杂度来源。可以清晰地看到，外层是一个循环，内层也是一个循环。外层循环控制整个排序的轮数，内层循环则处置惩罚每一轮中元素的比力与互换。
具体来说，外层循环执行的次数是 count，内层循环的次数是 count - 1。这意味着团体的操作次数是 count × (count - 1)，也就是 count² - count。虽然不是精确的 n 2 n^2 n2，但从复杂度增长的角度来看，这个量级依然是 O ( n 2 ) O(n^2) O(n2)。在大多数环境下，我们在分析算法时更关心增长的趋势而不是精确的操作数，所以这里的复杂度依然视为平方级别的增长。
为了避免混淆，我们也再次强调这个点。当我们说一个算法是 O ( n 2 ) O(n^2) O(n2) 的时候，我们指的是其操作数量的增长趋势——即随着数据量增加，执行次数以 n 2 n^2 n2 的速度增长。像 count² - count 如许的表达式，在数量非常大的时候，减去一个 count 根本上不会影响团体的增长趋势，所以仍然属于 O ( n 2 ) O(n^2) O(n2) 的范畴。
这也是为什么在分析复杂度时，通常只保留最高次项，并省略系数和低次项的原因。这种处置惩罚方式可以帮助我们快速明白算法在面对大规模数据时的表现，从而在选择算法或优化步调时做出更好的判定。
黑板：再次强调为什么在大 O 表示法中可以忽略加法项中的 n
我们之条件到的排序算法是冒泡排序（Bubble Sort），它的时间复杂度是 N 2 N^2 N2。这是因为在排序过程中，外层循环要进行 N N N 次，内层循环大约也要进行 N N N 次（精确来说是 N − 1 N-1 N−1 次），所以整个操作统共要执行 N × ( N − 1 ) N \times (N - 1) N×(N−1) 次，也就是 N 2 − N N^2 - N N2−N 次操作。
那么题目来了：如果运行时间是 N 2 + N N^2 + N N2+N，我们为什么只说是 N 2 N^2 N2 呢？
原因在于我们在谈论算法复杂度时，用的是渐进分析（asymptotic analysis），关注的是当输入规模 N N N 趋近于无穷大时，算法的增长趋势。
为什么忽略小项？
[*]当 N N N 很大时， N 2 N^2 N2 的增长速度远远快于 N N N。
[*]举例来说， N = 1 , 000 N = 1,000 N=1,000 时：
[*] N 2 = 1 , 000 , 000 N^2 = 1,000,000 N2=1,000,000
[*] N = 1 , 000 N = 1,000 N=1,000
[*]显然， N 2 + N = 1 , 001 , 000 N^2 + N = 1,001,000 N2+N=1,001,000，多出来那点几乎可以忽略不计。
[*]所以在复杂度分析中，我们只保留增长最快的项（也叫“主导项”），这就是 N 2 N^2 N2。
这也就表明了为什么我们说冒泡排序的复杂度是 O ( N 2 ) O(N^2) O(N2)，而不是 O ( N 2 + N ) O(N^2 + N) O(N2+N)。在大数据量的环境下， N N N 项根本没有什么影响，不会改变团体的增长趋势。
渐进分析的本质
这种处置惩罚方式本质上雷同于数学中的“极限”思想：
[*]就像我们在求函数极限时，只关注哪些项在趋于无穷时最有影响。
[*]小项在趋近极限的过程中“消失”，不会影响团体走势。
因此，算法复杂度分析中，我们也采用雷同做法，只关注最大项，从而得到一种对算法**可扩展性（scalability）**的统一度量。
现实影响如何？
虽然在小数据量下，低阶项和常数项会对运行时间产生影响，但一旦输入量增大，主导项就会“主导齐备”。这也意味着：
[*]如果一个算法是 O ( N 2 ) O(N^2) O(N2)，当数据规模增大到数千、数万，它的运行时间会迅速变得不可接受。
[*]哪怕另一个算法是 O ( N log N ) O(N \log N) O(NlogN)，纵然常数项较大，也能很快胜出。
结论
因此，我们在描述算法的时间复杂度时，通常只保留最高阶的项，忽略其他低阶项或常数项，这是权衡算法在大规模数据下的性能表现的核心方式。也就是说，我们不是说 N N N 不重要，而是在规模足够大时，它已经微不敷道，不再影响判定。
如果你还想继续深入，比如什么是 O ( N log N ) O(N \log N) O(NlogN) 或有哪些排序算法能达到这个复杂度，也可以继续讲下去~
黑板：只有当你真的要做“扩展”时，扩展性才重要！
在讨论排序算法时，大O符号（Order Notation）有时并不能完全揭示现实环境的复杂性，尤其是在数据规模较小时。大O符号的作用在于描述算法在处置惩罚大量数据时的表现，它非常擅长回答在大规模数据下，算法的时间复杂度如何增长。然而，当数据量较小时，大O符号无法很好地反映出不同算法之间的眇小差异。
1. 大O符号的局限性
大O符号的重点在于数据量很大的环境。它告诉我们，当数据量趋近于无穷大时，算法的运行时间是如何增长的。但是，在数据量较少时，不同算法的表现可能差别很大。这是因为在小数据规模下，算法的常数项（即固定的开销）对运行时间的影响较大。
2. 常数项的重要性
常数项在不同的算法中可能有所不同。当我们计算一个算法的执行时间时，通常会写出雷同以下的公式：
C × N 2 + C 1 × N + C 0 C \times N^2 + C_1 \times N + C_0 C×N2+C1×N+C0
其中， C C C 表示与 N 2 N^2 N2 相关的执行本钱， C 1 C_1 C1 表示与线性项（ N N N）相关的本钱， C 0 C_0 C0 是固定开销，不管数据量多大，它的本钱都是恒定的。
[*]当 N N N 很小的时候，这些常数项的影响可能会显着改变现实的运行时间。
[*]比如，如果 C 1 C_1 C1 很大，而 C 0 C_0 C0 是一个固定的值，那么在处置惩罚小规模数据时， N N N 和常数项可能会让一个理论上 O ( N 2 ) O(N^2) O(N2) 的算法比其他算法运行得更快。
3. 大规模数据时的厘革
但是，一旦数据规模非常大，常数项就变得不那么重要了。对于非常大的 N N N（如数十亿、数万亿甚至更大），纵然某个项的常数非常大，最终最重要的仍然是最高阶的项。例如：
[*]当 N N N 非常大时， N 2 N^2 N2 的增长速度远远高出 N N N 或常数项，因此对于极大数据量的处置惩罚，常数项和低阶项几乎可以忽略不计。
4. 现实应用中的题目
尽管大O符号是用来分析大规模数据的表现，但在现实编程和游戏开发中，我们往往并不处置惩罚无穷大数据。相反，我们处置惩罚的是有限的数据集，这时常数项的影响变得非常关键。例如：
[*]在处置惩罚少量数据时，算法的常数项可能决定了哪个算法更符合。
[*]纵然某个算法的时间复杂度是 O ( N 2 ) O(N^2) O(N2)，如果常数项很小，且数据量不大，它可能比复杂度为 O ( N log N ) O(N \log N) O(NlogN) 的算法更快。
5. 总结
大O符号重要用于分析算法在数据量非常大的时候的表现，它让我们能够忽略常数项和低阶项的影响，关注重要的增长趋势。然而，在现实应用中，尤其是在处置惩罚较小的数据集时，常数项和低阶项的影响往往决定了算法的现实服从。所以在现实开发中，不能单纯依赖大O符号，还需要思量数据量的现实环境以及常数项的影响。
调试器：跳入 SortEntries 函数，查察 Count 的值
在这段过程中，起首是执行了一个典型的调用来存储实例，可能是在渲染一个过场动画。通过调用计数，我们可以看到当前的计数值渐渐厘革，刚开始是1。然后，我们尝试检查是否能够高出179。结果显示，计数值大约在80左右。接着我们继续运行游戏，查察过场动画的效果，计数值显示为100和160。
在这一过程中，计数的范围在特定的操作或过程下会有所厘革，可能与游戏运行中的某些事件或过程的进展有关。通过这些操作，可以观察到体系在不同阶段的表现和处置惩罚能力。
黑板：规模对结果的影响
在现实使用中，通常会碰到一个题目，就是在数量较小的时候，虽然算法的复杂度较高，但由于计算的元素并不多，计算开销反而并不显着。例如，如果一个算法的复杂度是 O ( N 2 ) O(N^2) O(N2)，而另一个是 O ( N ) O(N) O(N)，在现实使用时，可能这两个算法的运行时间差异并不会很大，尤其是当 N N N 较小的时候。
例如，当 N = 160 N = 160 N=160 时， N 2 = 25 , 600 N^2 = 25,600 N2=25,600。这时，计算25,600次操作，对于现代计算机来说并不会构成性能瓶颈，处置惩罚起来也不算很慢。所以在现实应用中，虽然一个算法是 O ( N 2 ) O(N^2) O(N2)，另一个是 O ( N ) O(N) O(N)，但如果计算的规模较小，两个算法的差距可能不会那么显着。
但是题目在于，当 N N N 较小时， O ( N 2 ) O(N^2) O(N2) 的算法和 O ( N ) O(N) O(N) 的算法的性能差距可能没有那么显着，这时甚至可能会碰到其他因素影响计算性能，比如缓存命中率。比如，如果一个算法 B B B 的操作非常不符合缓存的使用，导致频繁的缓存未命中（cache miss），而另一个算法 A A A 的操作则高度缓存友好，可能 B B B 的执行服从反而比 A A A 更慢。缓存未命中可能导致每次操作都需要等待数百个时钟周期，从而显着影响性能。
这种环境下，纵然算法 A A A 的复杂度是 O ( N 2 ) O(N^2) O(N2)，而 B B B 是 O ( N ) O(N) O(N)，由于 B B B 的不良缓存友好性，执行服从反而可能变得更慢。
然而，当题目的规模增大到极其庞大的时候（例如 N = 1 0 9 N = 10^9 N=109）， O ( N 2 ) O(N^2) O(N2) 的算法会变得非常慢，甚至无法接受，而 O ( N ) O(N) O(N) 的算法则可以处置惩罚得非常高效。这时，算法的复杂度差异就变得非常显着，算法 A A A 可能就不再适用了。
总之，虽然大多数时候我们关注的是算法复杂度和扩展性，但在较小规模的数据处置惩罚中，其他因素（如缓存优化、硬件特性等）可能会对现实性能产生更大的影响。
黑板：最坏环境分析
在讨论算法的复杂度时，特别是 O ( N 2 ) O(N^2) O(N2) 与 O ( N ) O(N) O(N) 的区别时，我们通常指的是最坏环境的运行时间。这意味着一个算法的复杂度可能是 O ( N 2 ) O(N^2) O(N2)，但是现实运行时，它的性能可能远好于最坏环境。例如，它可能在大多数环境下只需要 O ( N ) O(N) O(N) 的时间，甚至有时候在某些操作下它可能只需要 O ( 1 ) O(1) O(1) 的时间。最坏环境下的时间复杂度并不能完全代表算法在所有环境下的表现。
例如，快速排序（Quicksort）是一种典型的 O ( N 2 ) O(N^2) O(N2) 算法，但它在大多数环境下可以在 O ( N log N ) O(N \log N) O(NlogN) 时间内完成排序。尽管最坏环境下它的复杂度是 O ( N 2 ) O(N^2) O(N2)，但现实使用中它通常能够达到较快的速度。因此，当我们说快速排序是一个 O ( N 2 ) O(N^2) O(N2) 的算法时，现实上我们指的是它在最差环境下的性能，而不是它通常环境下的表现。
与之相比，归并排序（Merge Sort）是一个典型的 O ( N log N ) O(N \log N) O(NlogN) 算法。这里的 log N \log N logN 是以2为底的对数，表示一个非常平缓的增长函数。无论 N N N 有多大， log N \log N logN 的值都不会增长得很快，因此这种算法在处置惩罚大数据时非常高效。归并排序的复杂度 O ( N log N ) O(N \log N) O(NlogN) 表示它的运行时间随着数据量的增加而呈对数增长，相比之下， O ( N 2 ) O(N^2) O(N2) 的增长速度要快得多。
虽然归并排序的理论复杂度优于快速排序，但现实环境中，快速排序常常因为常数因子较小而表现得更好，尤其是在处置惩罚现实数据时。所以，虽然理论上的复杂度非常重要，但现实的执行时间还受到许多因素的影响，比如常数因子、缓存命中率等。
黑板：为什么 C 运行库默认使用 quicksort（快速排序）
在选择排序算法时，虽然有些排序算法理论上表现得更好，例如 O ( N ) O(N) O(N) 的线性排序，但现实上，许多库选择将快速排序（quicksort）作为默认排序算法，而不是选择一个简单的 O ( N 2 ) O(N^2) O(N2) 算法。这是因为，虽然快速排序在最坏环境下的时间复杂度是 O ( N 2 ) O(N^2) O(N2)，但它在大多数环境下的盼望时间复杂度是 O ( N log N ) O(N \log N) O(NlogN)，并且通常环境下，它比归并排序（merge sort）要快。
快速排序的现实表现常常比理论复杂度更好，尤其是在一些硬件环境下。比如，在开发 C 运行时库时，快速排序的现实运行速度通常优于其他排序算法。因此，库开发者选择快速排序作为默认排序算法，重要是思量到它在大多数现实应用中的服从，而不是最坏环境下的表现。
当然，在某些环境下，最坏的 O ( N 2 ) O(N^2) O(N2) 时间复杂度是一个潜在的风险。如果一个应用步调非常依赖实时性能，可能不渴望碰到极度环境下的性能下降。比如，如果排序算法在某些特定环境下变得非常慢，可能会影响到应用的响应速度，这就可能是一个不可接受的风险。然而，对于大多数应用步调来说，最坏环境发生的频率非常低，因此可以接受这一偶然发生的性能下降。
总之，明白大 O 复杂度时，必须区分最坏环境和均匀环境。最坏环境复杂度给出的只是理论上的上限，并不意味着每次都会达到这个极度环境。在现实应用中，许多时候我们更加关注的是盼望的运行时间，而不是理论上的最坏环境。
黑板：其他排序算法
在讨论排序算法时，常见的有几种算法，包括冒泡排序、归并排序、快速排序、基数排序和插入排序等。每种算法的实现方式和适用场景都有所不同。
[*] 冒泡排序（Bubble Sort）：
[*]冒泡排序是一种简单的排序算法，根本原理是通过重复互换相邻的元素，使较大的元素“冒泡”到列表的末尾，较小的元素则渐渐“沉淀”到列表的前端。它的时间复杂度是 O ( N 2 ) O(N^2) O(N2)，适用于小规模数据的排序。虽然实现简单，但由于它的服从较低，不得当处置惩罚大规模的数据。
[*] 归并排序（Merge Sort）：
[*]归并排序是一种分治算法，它通过递归地将数组分割成两半，对每一半进行排序，然后将排序好的两半合并成一个排序好的数组。归并排序的时间复杂度是 O ( N log N ) O(N \log N) O(NlogN)，它是稳定的排序算法，尤其适用于大规模数据的排序，但它需要额外的空间来存储暂时的数组。
[*] 快速排序（Quick Sort）：
[*]快速排序是一种非常高效的排序算法，采用分治策略。它通过选择一个“基准”元素，将数组分割为两部分，其中一部分的元素都小于基准，另一部分的元素都大于基准，然后对这两部分递归进行排序。尽管最坏环境下快速排序的时间复杂度为 O ( N 2 ) O(N^2) O(N2)，但它的盼望时间复杂度是 O ( N log N ) O(N \log N) O(NlogN)，并且在多数环境下比归并排序要更快。由于其快速的均匀表现，许多库默认采用快速排序作为排序算法。
[*] 基数排序（Radix Sort）：
[*]基数排序是一种非比力型排序算法，适用于数字或者其他按位可分的排序对象。它将数字按位分组，先按最低位排序，再按次低位排序，直到排序完成。基数排序的时间复杂度通常是 O ( N k ) O(Nk) O(Nk)，其中 k k k 是数字的位数。在数据规模较大且位数较少的环境下，基数排序的服从可能优于基于比力的排序算法。
[*] 插入排序（Insertion Sort）：
[*]插入排序是一种简单的排序算法，它通过构建有序的子序列来逐步插入元素。每次插入一个新的元素时，将其插入到已经排序好的子序列中，直到整个序列有序。插入排序的时间复杂度是 O ( N 2 ) O(N^2) O(N2)，但对于小规模数据，或者数据已经根本有序的环境下，插入排序可能比冒泡排序和选择排序更高效。
这些算法在现实应用中，选择何种排序算法取决于具体的使用场景。快速排序和归并排序由于其较好的时间复杂度，通常被广泛使用；而对于较小规模的数据或者部分已排序的数据，插入排序可能更符合。而在处置惩罚大量数据时，基数排序可能会是一个很好的选择，尤其是在数据的位数相对较少时。
黑板：这些排序在最坏环境下的预期运行时间
在讨论排序算法时，冒泡排序、归并排序和快速排序是三种常见的算法。它们在服从和实现上各有不同，适用的场景也各自不同。
[*] 冒泡排序（Bubble Sort）：
[*]冒泡排序的根本思路是：从列表的起始位置开始，比力相邻的两个元素，如果它们的序次不正确，就互换它们的位置。如许，较大的元素会渐渐“冒泡”到列表的末尾。通过不停重复这一过程，最终列表会变得有序。其时间复杂度为 O ( N 2 ) O(N^2) O(N2)，因为每一轮排序都需要遍历所有元素，并进行必要的互换。这种算法得当数据量较小的环境，但服从较低，不适用于大数据量的排序。
[*] 归并排序（Merge Sort）：
[*]归并排序是一种基于分治法的排序算法。它将数组递归地分成两半，分别排序，然后再合并这两半。归并排序的时间复杂度为 O ( N log N ) O(N \log N) O(NlogN)，比冒泡排序更高效。虽然归并排序在大多数环境下表现精彩，但它的缺点是需要额外的空间来存储暂时的数组，这使得它的空间复杂度为 O ( N ) O(N) O(N)。
[*] 快速排序（Quick Sort）：
[*]快速排序是一种分治算法，它通过选择一个“基准”元素，将数组分割成两个部分，一部分所有元素都小于基准，另一部分所有元素都大于基准。然后递归地对这两个部分进行排序。快速排序的均匀时间复杂度是 O ( N log N ) O(N \log N) O(NlogN)，但最坏环境下可能达到 O ( N 2 ) O(N^2) O(N2)，这通常发生在基准选择不理想时。不外，通过改进选择基准的策略（比如随机选择基准），可以大大低落最坏环境发生的概率，使得它在实践中常常比其他排序算法更高效。快速排序在许多编程语言的标准库中作为默认排序算法，因其在大多数环境下的优异性能。
总结来说，冒泡排序虽然实现简单，但性能差，得当小规模数据。归并排序则适用于大数据量，尽管它需要额外的空间。快速排序则在大部分环境下表现最好，尤其是在没有特别严格最坏环境要求的场景下。
黑板：快速排序教学
快速排序（Quicksort）是一种基于分治法的排序算法，它的根本思想是通过选择一个“基准”元素，将数组分成两部分，一部分包含所有比基准小的元素，另一部分包含所有比基准大的元素。然后递归地对这两部分进行排序。快速排序的均匀时间复杂度是 O ( N log N ) O(N \log N) O(NlogN)，但是在最坏环境下，它的时间复杂度会变成 O ( N 2 ) O(N^2) O(N2)。
快速排序的核心步骤如下：
[*] 选择基准（Pivot）：起首，选择一个元素作为基准，可以是数组中的任何元素。在现实应用中，通常选择第一个元素、末了一个元素或随机选择一个元素作为基准。
[*] 分区过程（Partitioning）：根据基准元素，将数组分成两部分：一部分包含所有小于基准元素的元素，另一部分包含所有大于或等于基准元素的元素。这一过程称为分区。分区的过程中，基准元素会被放置到它最终应该在的排序位置。
[*] 递归排序：对分区后的两部分分别递归地应用相同的操作，即再次选择基准、分区、递归排序，直到每部分只剩下一个元素或没有元素为止，此时数组就变得有序。
时间复杂度分析：
[*] 最坏环境：如果每次选择的基准元素总是数组中的最大值或最小值，分区后数组的两部分会非常不均衡，导致递归深度过大。此时，快速排序的时间复杂度会退化到 O ( N 2 ) O(N^2) O(N2)，因为每一轮只会减少一个元素，最多需要进行 N N N 轮递归。
例如，如果每次都选择最大的元素作为基准，那么第一轮排序后只会有一个大于基准的子数组，递归时每次只能处置惩罚一个元素，最终时间复杂度是 O ( N 2 ) O(N^2) O(N2)。
[*] 均匀环境和盼望环境：快速排序的均匀时间复杂度是 O ( N log N ) O(N \log N) O(NlogN)。这种环境发生在每次选择的基准能够将数组大致分成两半，递归的深度为 O ( log N ) O(\log N) O(logN)，每一层的操作复杂度为 O ( N ) O(N) O(N)，因此团体时间复杂度为 O ( N log N ) O(N \log N) O(NlogN)。
为什么快速排序通常比归并排序快：
尽管快速排序的最坏环境是 O ( N 2 ) O(N^2) O(N2)，但在现实应用中，最坏环境发生的概率非常小。通常环境下，基准元素选择较好，可以将数组大致均匀地分成两部分，如许递归的深度保持在 O ( log N ) O(\log N) O(logN) 左右，使得快速排序的现实表现通常要优于归并排序。尤其是当数据量很大的时候，快速排序的常数因素较小，因此会表现得更快。
快速排序的优化：
为了避免最坏环境的发生，可以采用以下几种方法来优化快速排序：
[*] 随机化基准选择：通过随机选择基准元素，避免在输入数据已经是有序或接近有序的环境下出现最坏环境。
[*] 三数取中法：选择数组的第一个元素、末了一个元素和中心元素的中位数作为基准，以提高基准选择的质量，减少最坏环境的发生。
总结：
快速排序是一种非常高效的排序算法，均匀时间复杂度为 O ( N log N ) O(N \log N) O(NlogN)，尽管最坏环境下可能退化到 O ( N 2 ) O(N^2) O(N2)，但通过随机化或优化基准选择，可以显着减少最坏环境的概率。在现实应用中，由于其较小的常数因子，快速排序通常比其他排序算法如归并排序更快，尤其是在处置惩罚大量数据时。
好的，下面我将通过一个简单的例子来展示快速排序的工作过程。
假设我们有一个数组：
步骤 1：选择基准元素
起首，快速排序需要选择一个 基准元素。在这里，我们假设我们总是选择数组的第一个元素作为基准（现实应用中可以随机选择）。因此，基准元素就是 5。
步骤 2：划分数组
根据基准元素 5，我们将数组划分为两个部分：
[*]小于5的部分：
[*]大于5的部分：
此时，基准元素 5 已经被放置在它正确的位置。数组变成了：
步骤 3：递归对两个部分进行排序
如今我们递归地对两个部分进行快速排序。
对左边部分 进行排序：
[*]选择基准元素 2。
[*]划分为：
[*]小于2的部分：
[*]大于2的部分：
基准元素 2 被放置在正确的位置，数组变成：
接下来，我们分别对 1 和 进行排序：
[*] 已经是有序的，不需要再处置惩罚。
[*]对 进行排序，选择 3 作为基准：
[*]小于3的部分：[]
[*]大于3的部分：
基准元素 3 被放置在正确的位置，最终 已经排序好。
到此为止，左边部分 完成了排序，变成了
。
对右边部分 进行排序：
[*]选择基准元素 9。
[*]划分为：
[*]小于9的部分：
[*]大于9的部分：[]
基准元素 9 被放置在正确的位置，数组变成：
接下来，我们对 进行排序：
[*]选择基准元素 7。
[*]划分为：
[*]小于7的部分：
[*]大于7的部分：
基准元素 7 被放置在正确的位置，最终 已经排序好。
数组变成了：
[1, 2, 3, 4, 5, 6, 7, 8, 9
]
步骤 4：完成排序
到此为止，整个数组已经排序完成。
最终的有序数组是：
[1, 2, 3, 4, 5, 6, 7, 8, 9
]
总结
快速排序的核心思想是通过选择一个基准元素，将数组分成两个部分，然后递归地对这两个部分进行排序。在每次递归时，数组会被不停划分，直到每个子数组只有一个元素，最终完成排序。
黑板：如何选择枢轴元素
快速排序的一个关键点是基准元素的选择。基准元素的选择直接影响排序过程的服从，因此在实现快速排序时，如何选择基准元素非常重要。
如果知道输入数据的特点，例如数据的分布范围，或者数据是如何分列的，就可以根据这些信息选择符合的基准，避免最坏环境的发生。例如，如果已知数据的值在某个范围内且匀称分布，那么可以选择这个范围的中心值作为基准。由于数据匀称分布，选择中心值作为基准将使得数组被大致均匀地分成两部分，从而提高排序服从，避免出现最坏的 O ( N 2 ) O(N^2) O(N2) 时间复杂度。
因此，快速排序的表现不仅取决于算法自己，还依赖于对数据的了解。如果能提前知道数据的特性，可以选择符合的基准，使得快速排序在现实使用中避免最坏环境的发生，从而保证排序的高效性。这种策略也雷同于随机化算法的思想，通过引入一些随机因向来确保基准选择不至于导致严重的不均衡分区。
举个例子，如果你知道你的数据是按某种规律分布的，比如数据值的最小值和最大值已知且匀称分布，那么选择范围的中值作为基准就是一个很好的选择。如允许以保证每次分区时都能较为匀称地分配数据，避免快速排序退化到最坏的时间复杂度 O ( N 2 ) O(N^2) O(N2)。
总的来说，尽管快速排序的理论最坏环境时间复杂度是 O ( N 2 ) O(N^2) O(N2)，但是通过对数据的深入明白和符合的基准选择，可以大大减少最坏环境发生的概率，从而使得快速排序在现实应用中表现得更加高效。在特定环境下，选择符合的基准，甚至通过随机化选择基准，能保证快速排序的服从远高于其最坏环境。
黑板：用随机性优化算法运行时间的可能性
如果快速排序总是选择列表中的第一个值作为基准，那么几乎可以确保它会在最坏环境下运行 O ( N 2 ) O(N^2) O(N2) 的时间复杂度。这种环境发生在数据自己已经是有序的环境下，比如说在渲染队列中，Z轴的值是按序次递增的：1, 2, 3, 4, 5, 6, 7。因为在这种环境下，选择第一个元素作为基准会导致每次划分时，基准总是排在最前面，导致每次分区只清除一个元素，剩下的元素仍然需要排序，从而退化为 O ( N 2 ) O(N^2) O(N2)。
为了避免这种最坏环境的发生，可以采用随机化的方法。具体来说，可以先随机打乱所有元素的序次，再进行快速排序。通过这种方式，算法在每次运行时都不会产生相同的基准选择，从而大大低落了出现最坏环境的可能性。这意味着无论数据的初始序次如何，快速排序都能够以一种较为“混乱”的方式开始，从而避免了每次都选择到最坏的基准。
尽管这种方法可以有效地减少最坏环境的出现，但使用随机化算法并不是每个场合下都能接受的做法。有时，如果已经了解数据的特点，可以直接将这些信息融入到排序算法中，选择更符合的排序方式，而不必依赖随机化。但如果目标是编写一个通用的排序算法，那么使用随机化策略可以帮助确保算法在面对不同类型的数据时表现稳定，减少出现极度性能题目的几率。
总结来说，通过引入随机化，可以避免因输入数据的特定序次导致快速排序退化为最坏环境 O ( N 2 ) O(N^2) O(N2)。这种方法适用于通用排序算法，但对于已知数据特性时，照旧更倾向于直接使用其他更符合的排序算法。
举个例子来帮助更好地明白快速排序和如何通过随机化避免最坏环境。
假设我们有一个已经按升序分列的数据：
1, 2, 3, 4, 5, 6, 7, 8, 9
如果我们使用传统的快速排序，假设每次总是选择第一个元素作为基准（pivot）。那么第一次划分时，基准元素是 1，所有比 1 小的元素都没有，因此所有剩下的元素 都被划分到右边。这时，我们就会有雷同下面的递归调用：
[*]第一次选择基准 1，划分出 。
[*]继续递归，基准 2，剩下 。
[*]再次递归，基准 3，剩下 。
[*]如此类推，直到末了，所有元素依然未排序，快速排序的时间复杂度变为 O ( N 2 ) O(N^2) O(N2)。
这就是快速排序的最坏环境，特别是在输入数据已经有序时，快速排序的服从极低。
通过随机化避免最坏环境
为了避免这种最坏环境，可以通过 随机化选择基准元素 来改善排序服从。假设我们随机打乱一下输入数据：
6, 2, 8, 1, 4, 9, 3, 7, 5
此时快速排序会选择一个随机的元素作为基准，而不是总是选择第一个元素。假设我们第一次随机选择 4 作为基准，那么会将数组分成两个部分：
[*]小于 4 的部分：
[*]大于 4 的部分：
此时，基准 4 将被放置在正确的位置。然后我们对两个子数组继续进行快速排序，分别选择新的基准值，如 2、6 等。
由于每次选择的基准不同，分割后的子数组也会不同，且大多数环境下能够很好地平衡数据的分布，因此不会退化到最坏环境。现实上，随着元素数量增加，随机化的基准选择使得每次分割通常会比力匀称，从而让算法的盼望时间复杂度接近 O ( N log N ) O(N \log N) O(NlogN)。
具体例子
假设我们有数组：
[*] 第一步：选择随机基准元素。假设随机选择 6 作为基准。
[*]小于 6 的部分：
[*]大于 6 的部分：
[*]基准元素 6 被放置在它正确的位置。
[*] 第二步：递归对子数组进行快速排序。
[*] 对 进行排序，假设选择 3 作为基准：
[*]小于 3 的部分：
[*]大于 3 的部分：
[*]基准元素 3 被放置在它正确的位置。
[*] 对 进行排序，假设选择 7 作为基准：
[*]小于 7 的部分：[]
[*]大于 7 的部分：
[*]基准元素 7 被放置在它正确的位置。
[*] 继续递归直到数组完全排序。
通过这种方式，快速排序避免了每次都选择最坏的基准，从而低落了退化为 O ( N 2 ) O(N^2) O(N2) 的可能性。
总结
通过随机化选择基准，可以显着减少最坏环境的发生概率。纵然数据输入有某种特定的序次，通过打乱数据，可以避免每次都选到最坏的基准，从而保证快速排序大多数环境下具有较好的性能，接近 O ( N log N ) O(N \log N) O(NlogN)。
黑板：基数排序（Radix sort）
基数排序（Radix Sort）
基数排序是一种与传统排序算法有所不同的排序方法，常常被误解为是O(1)复杂度的排序，但现实上它的时间复杂度是O(kn)，其中k是每个元素的位数（或者说是"数字"的个数），n是待排序元素的个数。基数排序重要利用了计算机在存储数据时具有的固定大小，来优化排序过程。
基数排序的根本原理
基数排序的核心思想是按位排序。我们知道计算机内部处置惩罚的数字一样平常是固定大小的，比如32位整数、64位整数等。基数排序假设这些数字的大小是已知的，并且可以根据数字的位（或字节）进行排序。
[*] k 是数字的位数（或“数字”的个数），这与排序的范围有关。比如在32位整数中，数字有32个二进制位，基数排序会对这些位进行逐一处置惩罚。
[*] 基数排序的工作方式是：起首按照最低位（或最高位）开始排序，然后逐位排序，直到所有位都处置惩罚完为止。
具体工作过程
假设我们要排序的是32位的整数数组。基数排序会按位来进行排序：
[*] 第一步：起首根据最低有效位（最右边的位）进行排序。这个排序会把所有数字分成两组：低位为0的数字和低位为1的数字。
[*] 第二步：根据第二位排序，将第一步排序后的结果再次按第二位分组，继续进行排序。
[*] 继续对每一位进行排序，直随处置惩罚完所有32位数字。
在每一步排序时，我们将数字分配到不同的“桶”中，根据该位的值。每次排序后，桶中的元素会按序次合并，形成一个新的数组，直到所有位都排序完毕。
时间复杂度
[*]n 是待排序元素的数量。
[*]k 是数字的位数（例如，对于32位整数，k=32）。
[*]因此，基数排序的时间复杂度是 O(kn)，其中n是元素个数，k是数字的位数。
需要留意的是，这里并没有使用对数运算（log n），与许多基于比力的排序算法（如快速排序、归并排序）不同。
空间复杂度
基数排序需要额外的空间来存储桶和排序过程中的中心结果，因此它不是一种原地排序（in-place sorting）算法。这意味着基数排序需要额外的空间来存储每个桶的内容。不外，除非空间极其有限，通常这不会成为一个题目。
基数排序的应用场景
基数排序并不适用于所有排序任务，它特别得当于排序固定大小的整数或字串，尤其是在范围固定且较为“规则”的环境下。例如，排序32位或64位的整数、或者对有特定格式的字符串排序时，基数排序的服从较高。
总结
基数排序是一种通过逐位排序来处置惩罚数字的高效排序算法。它利用了计算机处置惩罚固定大小数据的特点，避免了使用对比操作，因此在处置惩罚大规模数据时，特别是数字范围已知且数据分布相对规则的环境下，基数排序能提供优于传统排序算法的性能。
下面通过一个简单的例子来展示基数排序的具体过程。
假设我们有以下待排序的数组：
我们将按位进行排序，起首从最低位（个位）开始，然后依次处置惩罚十位、百位等，直到排序完成。
步骤 1：按个位（最低位）排序
我们将所有数字按照个位的数字排序，得到以下结果：
数字个位数1700802222244455755666900 排序结果：
步骤 2：按十位排序
如今根据十位上的数字重新排序：
数字十位数1707802020242454757666909 排序结果：
步骤 3：按百位排序
接下来，按百位排序：
数字百位数8028202404506601701750900 排序结果：
完成排序
最终结果是：
总结
基数排序通过逐位处置惩罚数字（从最低位到最高位），将所有数字按位排序，直到排序完成。在此过程中，每一位的排序会将数字分到不同的桶里，然后按序次将它们合并，从而实现整个数组的排序。
通过此例可以看出，基数排序的关键在于将数据分解成多个较小的部分，逐步进行排序，不依赖于数字的大小，而是依赖于每一位的值进行分类。
黑板：（伪）插入排序
插入排序是一种简单的排序算法，时间复杂度是 O ( n 2 ) O(n^2) O(n2)。它的工作原理是逐步将未排序的元素插入到已排序的部分中。在每一步中，它会把一个元素插入到正确的位置，这个过程需要比力并移动已排序部分的元素。
插入排序的工作流程：
[*]初始化： 从第二个元素开始，假设第一个元素已经排好序。
[*]插入元素： 对于当前待插入的元素，逐一与已排序部分的元素进行比力，将比它大的元素向后移动。
[*]插入位置： 找到符合的位置后，把待插入的元素放进去。
[*]重复步骤： 对每个未排序的元素重复这个过程，直到所有元素排好序。
复杂度分析：
[*]插入排序的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，因为在最坏的环境下，每个元素都可能需要与已排序部分的所有元素进行比力和移动。因此，对于 n n n 个元素，需要进行大约 n n n 次插入操作，每次插入都可能涉及 n n n 次比力和移动。
[*]纵然使用链表来实现插入排序，不需要移动车阵中的所有元素，仍然需要比力所有元素，因此最坏环境依然是 O ( n 2 ) O(n^2) O(n2)。
特别环境：伪插入排序
尽管插入排序在团体排序中服从较低，但在某些特别环境下，它照旧有用的。比如，当我们只关心找到最大或最小的前几个元素时，插入排序非常高效。例如：
[*]如果有一个包含1000个元素的列表，而我们只关心其中的前4个最大值，使用插入排序可以通过维护一个小的排序列表（如4个元素）来快速找到这些最大值。
[*]在这种环境下，插入排序会将每个元素与当前已排序的4个元素进行比力，并插入到正确的位置，如许每次操作的时间复杂度是 O ( 4 × n ) O(4 \times n) O(4×n)，因此总的时间复杂度为 O ( n ) O(n) O(n)，远远高于全排序的 O ( n 2 ) O(n^2) O(n2)。
这种方法叫做“伪插入排序”，因为我们并没有对所有元素进行排序，只是在一个小的排序区域内进行插入操作，快速找到我们关心的前几个元素。
总结来说，虽然插入排序并不是一个高效的排序算法，但它在特定环境下（如寻找前几个最大或最小元素）非常有用，尤其是当我们只需要部分排序时，它能提供较高的服从。
让我们通过一个具体的例子来更好地明白插入排序的工作原理，并看一下如何使用“伪插入排序”来解决一些特定的题目。
插入排序例子：
假设我们有一个包含 5 个整数的列表：
5 , 2 , 9 , 1 , 5 5, 2, 9, 1, 5 5,2,9,1,5
步骤 1: 从第二个元素开始，假设第一个元素已经排好序。
[*]当前列表： 5 ∣ 2 , 9 , 1 , 5 5 | 2, 9, 1, 5 5∣2,9,1,5
步骤 2: 插入 2。
[*] 2 小于 5，因此我们将 5 向右移动一位，插入 2 到第一个位置。
[*] 当前列表： 2 , 5 ∣ 9 , 1 , 5 2, 5 | 9, 1, 5 2,5∣9,1,5
步骤 3: 插入 9。
[*] 9 大于 5，因此我们不需要移动 5，将 9 插入到已排序部分的末尾。
[*] 当前列表： 2 , 5 , 9 ∣ 1 , 5 2, 5, 9 | 1, 5 2,5,9∣1,5
步骤 4: 插入 1。
[*] 1 小于 9、5 和 2，因此我们需要将这些元素依次向右移动，然后将 1 插入到最前面。
[*] 当前列表： 1 , 2 , 5 , 9 ∣ 5 1, 2, 5, 9 | 5 1,2,5,9∣5
步骤 5: 插入 5。
[*] 5 等于 5，所以我们将第一个 5 向右移动，然后将新的 5 插入到第二个 5 之前。
[*] 最终排序后的列表： 1 , 2 , 5 , 5 , 9 1, 2, 5, 5, 9 1,2,5,5,9
在这个例子中，插入排序通过一次次将元素插入到已排序部分来逐步完成排序。每次插入操作的时间复杂度是 O ( n ) O(n) O(n)，而团体时间复杂度是 O ( n 2 ) O(n^2) O(n2)，因为在最坏环境下，每次插入都需要与所有已排序的元素进行比力。
伪插入排序例子：
假设我们有一个包含 1000 个元素的列表，但我们只关心其中的前 3 个最大值。使用“伪插入排序”方法，我们可以创建一个大小为 3 的小列表来存储当前最大的 3 个元素。
假设列表中的 5 个元素是：
5 , 2 , 9 , 1 , 5 5, 2, 9, 1, 5 5,2,9,1,5
我们想要找到其中的最大 3 个元素。
步骤 1: 初始化一个空列表或一个包含 3 个最大值的列表（这里我们先初始化为空）：
_ , _ , _ \_ , \_ , \_ _,_,_
步骤 2: 插入第一个元素 5。
[*]当前列表： 5 , _ , _ 5, \_ , \_ 5,_,_
步骤 3: 插入第二个元素 2。
[*] 2 小于 5，因此 2 不进入已排序列表，当前最大值列表保持稳定。
[*] 当前列表： 5 , _ , _ 5, \_ , \_ 5,_,_
步骤 4: 插入第三个元素 9。
[*]9 大于当前的最大值 5，因此 9 替换掉 5，新的最大值列表为： 9 , 5 , _ 9, 5, \_ 9,5,_
步骤 5: 插入第四个元素 1。
[*] 1 小于当前的最大值 9 和 5，因此 1 不进入最大值列表，当前最大值列表保持稳定。
[*] 当前列表： 9 , 5 , _ 9, 5, \_ 9,5,_
步骤 6: 插入第五个元素 5。
[*]5 等于当前最大值中的一个，因此仍然保留在最大值列表中，当前最大值列表保持为： 9 , 5 , 5 9, 5, 5 9,5,5
此时，我们只关心最大值列表中的前 3 个元素，而不需要对整个列表进行排序。因此，通过“伪插入排序”，我们能够高效地找出最大值。
总结：
[*] 插入排序适用于需要完全排序的环境。它的时间复杂度是 O ( n 2 ) O(n^2) O(n2)，在元素较少时效果较好。
[*] 伪插入排序常用于只关心部分排序的环境，尤其是找出列表中的前几个最大值或最小值。通过维护一个小的排序列表，插入排序可以高效地找到这些值，而不需要对整个列表进行完全排序。
这两种排序方法各有特点，插入排序在小规模数据集或部分排序需求下仍然很有用。
那为什么不总是使用 radix sort，直接 sort(sizeof(<类型>), data_) 呢？
我们在现实使用中并不会总是选择基数排序（Radix Sort），即便它的时间复杂度在理论上是 O ( k n ) O(kn) O(kn)，其中 k k k 是数据中“数字位数”的数量。原因有许多，下面是对其中关键点的详细总结和表明：
为什么我们不会总是用基数排序：
一、基数排序并不适用于所有数据类型
基数排序要求待排序的键必须可以被分割为“可比力的数字位”——比如整数的每一位或者比特位。如果我们要排序的是：
[*]浮点数（特别是有负数的环境）
[*]字符串（长度可变，字符集复杂）
[*]自界说对象（可能排序规则很复杂）
那么直接用基数排序就会变得麻烦甚至不可行。而比力类排序（如快速排序、归并排序）适用性更广，只要能界说比力函数就可以排序。
二、基数排序依赖于稳定的排序算法和辅助空间
在基数排序的每一轮中，我们按照“某一位”将元素分桶，这个过程通常需要额外空间：
[*]我们需要为每个桶分配内存来暂时存储元素。
[*]每一轮都要把元素移入移出这些桶，涉及复制或移动数据。
当我们内存告急，或者数据体量非常大，频繁的内存分配、复制可能导致性能下降。而像快速排序则可以原地排序，不需要额外空间。
三、基数排序的常数因子可能较大
虽然理论时间复杂度是线性的，但这并不意味着现实运行速度一定快。影响因素包括：
[*]如果我们每次按 1 bit 或 1 byte 来分桶，轮数 k k k 就会变多；
[*]如果我们一次处置惩罚多个 bit，比如按 8 bit 来分成 256 个桶，虽然轮数变少，但桶的数量增加，内存访问变得不一连，CPU 缓存友好性低落；
[*]桶操作（分配、复制、回写）自己开销不小；
[*]数据分布不均时，某些桶会特别大，局部退化。
这些常数开销可能让现实运行时间反而不如 O ( n log n ) O(n\log n) O(nlogn) 的快速排序。
四、基数排序要求数据位数是“固定且已知的”
例如我们知道一个整数是 32 位无符号整数，我们可以固定轮数为 4 次（每次按 8 位处置惩罚），统共 4 次 pass。但如果我们排序的对象是：
[*]长度可变的字符串
[*]非定长的 ID 或编码
[*]不清晰最大最小值的数字
我们就无法提前知道要分几轮，基数排序的实现就变得不确定，甚至会失败。
五、在某些环境下，快速排序能更好地处置惩罚“部分有序”的数据
比如：
[*]数据已经根本有序，只需少量调解；
[*]数据是从另一个体系中读取，已经有特定规律；
[*]快速排序的分区操作会非常高效。
基数排序则无法利用这些数据的特性，它的每一步处置惩罚都是一视同仁的固定逻辑。
举个例子说明：
假设我们要排序一百万个 ID：
"AB123", "XY456", "CD789", ...
这些 ID 是由两位大写字母 + 三位数字组成的字符串。
虽然它们在结构上是可以拆分成“字符 + 数字”，但：
[*]字符部分是字母，数字部分是十进制；
[*]字符与数字的排序优先级可能不同（比如按字母排序，再按数字）；
[*]字符串长度固定但字符集较复杂，分桶可能需要上百个；
[*]基数排序实现起来麻烦，服从未必高。
此时，如果使用快速排序并提供一个自界说比力函数：
def compare(id1, id2):
if id1[:2] != id2[:2]:
return id1[:2] < id2[:2]
return int(id1) < int(id2)
共同标准的排序算法，我们很容易完成任务，逻辑简单、服从高、内存占用少。
总结一下
虽然基数排序在特定条件下性能很好，但它的适用范围有限，受限于数据类型、空间需求和实现复杂度。我们并不会在所有环境下都使用它，通常只有在：
[*]数据是定长的整数（如 32 位或 64 位）
[*]数据量非常大
[*]内存资源富足
[*]排序稳定性有保障
这些条件下，它才会优于通例的比力排序。在大多数现实场景中，我们更倾向于选择快速排序、归并排序或者混合排序（如 Timsort）来平衡速度、空间和代码复杂性。
黑板：根据数据集选择最符合的排序算法
我们知道，一样平常的排序在最坏环境下的时间复杂度下限是 O ( n log n ) O(n \log n) O(nlogn)，这个下限已经被数学上严格证实，也就是说在通用比力排序模子下，不可能存在比 O ( n log n ) O(n \log n) O(nlogn) 更快的算法。例如归并排序（Merge Sort）、堆排序（Heap Sort）等都可以稳定地达到这个下限。而快速排序虽然均匀表现优秀，但最坏环境下仍然是 O ( n 2 ) O(n^2) O(n2)。
那么为什么我们不用看起来更快的基数排序（Radix Sort）来替代这些比力类排序算法呢？这里面有许多现实的思量。
一、基数排序是 O ( k n ) O(kn) O(kn)，但 K 不一定比 log n \log n logn 小
基数排序的复杂度是 O ( k n ) O(kn) O(kn)，其中：
[*] k k k 表示关键字的长度（例如一个 32 位整数可能分为 4 个 8-bit 字段）；
[*] n n n 是待排序元素个数。
如果我们排序的是一个包含 64,000 个元素的列表， log n \log n logn 大约是 16。而如果使用基数排序，每个元素的关键字是 32-bit，那我们也允许以只做 4 次 pass（每次处置惩罚 8-bit）。这时 k = 4 k=4 k=4，显着优于 log n = 16 \log n=16 logn=16。
但如果关键字是更长的，比如：
[*]一个 256 字节长的结构体；
[*]一个很长的字符串；
[*]一个复杂对象等。
此时 k k k 会远宏大于 log n \log n logn，例如可能是 64、128、甚至 256，如许基数排序的总本钱 k n kn kn 就会远高于 n log n n \log n nlogn。这就是为什么当排序字段足够复杂或足够长时，基数排序反而服从更低。
二、基数排序必须知道排序关键字的精确结构和长度
基数排序必须依赖于“可分桶”的关键字，例如：
[*]固定长度的整数；
[*]已知长度的字符串；
[*]明确格式的二进制表示。
但如果排序对象的关键字段是变长的或不可预测的，就很难使用基数排序。例如：
[*]排序名字（字符串），长度不定；
[*]排序路径、编码、UUID等不规则内容；
[*]排序某个计算结果，例如函数值。
在这种环境下，要使用基数排序，必须先预处置惩罚所有数据，找出最长的关键字，才气决定要分多少轮、每轮要处置惩罚多少位。这会带来额外的遍历开销，而比力排序则可以直接进行，无需提前分析所有元素。
三、基数排序不支持复杂的比力逻辑
比力排序可以灵活地使用自界说比力函数。比如我们可以写出下面的规则：
[*]名字按字母排序，但如果碰到“Carl”和“Dave”的组合，强制让“Carl”排前；
[*]如果某个对象的值是另一个值的函数结果，需要根据函数的值排序；
[*]排序逻辑中允许加入一些“例外规则”或跨字段判定。
这些在基数排序中是难以实现的。因为基数排序只依赖于“固定格式的键”，而不支持动态判定或分支逻辑。要实现这些逻辑，我们不得不在排序前将所有这些特别规则“烘焙”进排序键中，制作出一组精确的位串。这既复杂又低效。
四、比力排序不关心关键字长度，顺应性强
比力排序只在需要的时候才比力两个元素，它不关心关键字的长度。无论是：
[*]长度可变的字符串；
[*]巨大的结构体；
[*]动态计算出的排序指标。
只要界说一个比力函数，比力排序就可以处置惩罚。而基数排序要求每个元素在排序前就要“准备好”一串可比力、可分桶的键。这会让它在非结构化数据中变得不实用。
五、某些环境下比力排序更节省资源
基数排序：
[*]多次遍历数据（每一轮都要重排）；
[*]分桶复制或移动元素；
[*]空间复杂度较高；
[*]对缓存不友好（桶访问分散）。
比力排序如归并排序、快速排序在现代 CPU 架构下通常更友好，尤其是在数据局部性、内存访问和 CPU 分支预测方面做得更好。
举例说明：
假设我们要排序一批“实体对象”，每个实体有一个字段 name，这个名字可能是任意长度的字符串，比如：
[*]“Dave Bauer”
[*]“Carl Worthington”
[*]“Big Tuna”
我们要将这些实体按名字字母序次分列。并且加入一个特别规则：
“Carl” 总是排在 “Dave” 之前。
用比力排序，只需要写一个比力函数即可处置惩罚：
def compare(a, b):
if a.name.startswith("Carl") and b.name.startswith("Dave"):
return -1
if a.name.startswith("Dave") and b.name.startswith("Carl"):
return 1
return a.name < b.name
如许不仅灵活，还可以应对所有异常和边界环境。
但如果用基数排序，我们必须：
[*]找出最长名字；
[*]按位编码成等长的二进制键；
[*]加入特别规则的处置惩罚逻辑，把“Carl”强制排在“Dave”前；
[*]执行多轮桶排序。
这不仅复杂，而且性能可能更差。
总结
虽然基数排序在特定条件下非常高效（如 32 位整数排序），但它的适用场景很有限：
[*]必须是固定长度、结构化的关键字；
[*]必须能够预先计算关键字长度和格式；
[*]不允许太多复杂的比力逻辑和例外。
相比之下，比力类排序算法具有更高的灵活性、顺应性和现实服从，因此我们并不会总是选择基数排序。我们通常会根据数据结构和需求选择最符合的排序方式。
你有没有提到排序的稳定性？
排序的**稳定性（sort stability）**是一个非常重要但容易明白的概念。我们如今来详细说明：
一、什么是排序稳定性？
排序稳定性指的是：
当我们对一个包含多个相当键值的元素序列进行排序时，排序后这些相当元素之间的原有相对序次是否保持稳定。
简单说：
[*]如果两个元素在排序前比力结果是“相当”，排序之后它们仍然保持原来的前后位置序次，那么这个排序就是稳定的。
[*]如果排序之后，它们的位置可能互换，那这个排序就是不稳定的。
二、为什么排序稳定性很重要？
我们许多时候会进行多层排序（multi-key sort），也就是说，我们按某个字段排序完之后，还会再按另一个字段排序。
这个时候，稳定性保证了后续排序不会打乱前面已经排好的序次，从而实现“先按这个，再按谁人”的逻辑。
举个例子：
我们有一组人的数据，每人有“姓名”和“年龄”两个字段：
姓名年龄小张25小李20小王25小赵20 我们先按“姓名”字母排序（假设）：
姓名年龄小李20小王25小张25小赵20 然后我们再按“年龄”排序。如果排序是稳定的，结果会是：
姓名年龄小李20小赵20小王25小张25 如许同龄人之间还保留了前面按照“姓名”的序次。
但如果排序是不稳定的，则可能得到：
姓名年龄小赵20小李20小张25小王25 这就打乱了前面的序次，不再满足我们“先按姓名再按年龄”的需求。
三、哪些排序算法是稳定的？
稳定的排序算法：
[*]插入排序（Insertion Sort）✅
[*]归并排序（Merge Sort）✅
[*]冒泡排序（Bubble Sort）✅
[*]桶排序（Bucket Sort）✅
[*]计数排序（Counting Sort）✅
[*]基数排序（Radix Sort）✅（取决于实现）
不稳定的排序算法：
[*]快速排序（Quick Sort）❌
[*]堆排序（Heap Sort）❌
[*]选择排序（Selection Sort）❌
不外也要说明，许多排序算法的稳定性跟具体实现方式有关。比如：
[*]标准库里的快速排序版本可能做了稳定性优化；
[*]一些基数排序如果实现不当，也可能不稳定；
[*]某些基于比力的优化排序可能用混合方式来保持稳定性。
四、我们在什么场景需要稳定性？
稳定性在以下场景特别重要：
[*]多关键字排序（multi-key sort）：比如“先按部门，再按薪资”。
[*]可视化友好排序：UI 上让用户能感觉到逻辑不混乱。
[*]数据库查询结果排序：多字段排序时，反面的排序依赖前面的稳定性。
[*]日志、记载等带时序信息的数据：保证原有时间序次不被打乱。
总结
排序稳定性是排序算法的一个根本属性，指的是是否会在排序后保持原本相当元素的相对序次。
我们在涉及多层排序、UI展示、复杂业务逻辑时，非常依赖稳定性。
不是所有排序算法都是稳定的，我们要根据具体需求选择符合的排序方式，是否稳定往往会影响最终结果的正确性和可预期性。
黑板：排序稳定性教学
排序稳定性是排序算法中的一个重要概念，我们从一个具体例子出发来详细说明它的意义、作用以及应用场景。
一、什么是排序稳定性？
假设我们有一组待排序的数据如下：
abcadef
5923178
这里字母是排序的关键字（key），而每个字母反面对应的数字则是附带信息（不是用来排序的值）。我们渴望按字母升序排序。
排序结果会是：
aabcdef
??92178
其中 b 到 f 的序次唯一确定，毫无疑问。但“a”出现了两次，分别带有 5 和 3，我们想知道排序后的这两个“a”是按照什么序次排的。排序稳定性指的就是——当排序关键字相同时，原始数据的序次是否保留。
[*]如果保留，比如 a5 仍排在 a3 前面，那就是稳定的排序。
[*]如果序次被打乱，比如 a3 被排在 a5 前，那就是不稳定的排序。
二、排序稳定性有什么用？
我们可能会碰到许多需要“多层排序”的场景，比如在操作体系的文件管理器中，我们可能有一批文件，每个文件包含如下字段：
[*]文件名（name）
[*]创建日期（date）
[*]数量（比如吨数，tuna_quantity）
例如：
文件名日期吨数food.txtJuly 92inventory.txtJuly 95report.docxJuly 101 如果我们想按照以下逻辑排序：
[*]先按“吨数”降序排序；
[*]然后再按“日期”升序排序；
这时候如果排序算法是稳定的，我们可以：
[*]第一步：先排序吨数，从大到小分列；
[*]第二步：再按日期排序。
因为是稳定的排序，在第二步中，同一天（比如 July 9）的文件，还会保持吨数降序的序次，不会被打乱。
也就是说，稳定排序能让我们实现多层次的排序优先级控制。
三、排序稳定性的直观影响
继续举个简单例子，假设我们有一张数据表：
名字年龄Alice30Bob25Charlie30David25 如果我们先按“名字”排序，然后再按“年龄”排序，是否稳定就影响最终结果：
[*]稳定排序结果（按年龄）：
名字年龄Bob25David25Alice30Charlie30 因为 Bob 在 David 前，Alice 在 Charlie 前，保留了原序次。
[*]不稳定排序结果可能是：
名字年龄David25Bob25Charlie30Alice30 虽然年龄值一样，但名字序次被打乱了。
四、排序稳定性是否重要？
对于是否一定需要排序稳定性，其实视场景而定：
[*]在需要多关键字排序、数据层级处置惩罚或 UI 表格展示中，稳定性很有用；
[*]在对性能极致追求、排序字段单一、数据不敏感的场景，不稳定排序也完全可以接受；
[*]我们可能不会每次都关注它，但在需要的时候，稳定性是我们可以依赖的功能；
有时我们并不会显式要求排序稳定性，但一些底层库、数据库等已经自动提供了稳定排序，我们在使用时天然就得到了稳定行为。
总结
[*]稳定排序能保证相同关键字的元素保持原始序次；
[*]它是实现多层排序逻辑的基础；
[*]在许多现实场景中，尤其是面向用户的数据展示、体系表格排序、数据库操作等，都非常依赖排序稳定性；
[*]是否需要稳定性，取决于具体应用需求；
[*]对于开发排序逻辑或使用排序函数时，了解排序算法是否稳定，可以帮助我们做出更正确的选择。
除了精灵（sprites），我们还需要排序哪些内容？
我们在讨论排序时，除了精灵（sprites）以外，还可能需要排序其他内容，但目前尚不确定。也许最终只需要对精灵进行排序，也有可能会出现一两个其他需要排序的对象。
我们之所以思考这个题目，是为了提前思量排序算法的适用范围。如果我们将来确实还需要对其他类型的数据进行排序，那我们如今就必须确保所选的排序方法不仅适用于精灵，还能通用于其他类型的数据结构或逻辑。比如：
[*]排序游戏中的实体对象，例如 NPC、道具等；
[*]排序渲染队列，比如按照 Z 值或透明度来排渲染序次；
[*]排序 UI 元素，例如按钮、菜单、图层等；
[*]排序触发事件，比如定时器触发序次、任务调度等；
[*]排序资源加载，比如纹理加载优先级、网络请求队列等。
如果将来只对精灵排序，那我们可以针对精灵的特性去做一些专门优化，比如按 Z 值或屏幕位置排序。但如果还需要支持更多种类的排序，那就必须设计得更通用、可复用、稳定性好的排序体系，以便能够灵活应对不同数据类型和排序规则的需求。
因此，我们的结论是——虽然当前重要聚焦在对精灵的排序，但也要为将来可能的需求厘革做好准备，保持代码的扩展性和灵活性。如许，无论是否会出现其他需要排序的东西，我们都可以应对自若。
我们能不能通过提示或预天生地面块，让 radix sort 更高效？
我们在讨论地面区块（ground chunks）的排序方式时，提出了一个设想：是否可以以某种特定方式天生地面区块的“提示信息”或“键值”，以便更高效地使用基数排序（radix sort）来排序这些区块。
我们认为，基数排序或许自己就是一种对于我们当前应用场景而言相当理想的排序方式，可能在团体上就是最优的。但我们也承认这并不容易断言，还需要团结具体实现和现实测试才气下定论。
核心的思路是：如果我们能在天生地面区块时，就为其附带上得当基数排序的“排序键”（比如固定大小的整数或其他可按位拆分的结构），那么我们就能充分发挥基数排序的线性复杂度上风，从而提拔团体排序服从。
不外，这里存在一个条件条件，即我们所依赖的排序键必须满足以下特性：
[*]固定大小：基数排序的服从来自于它对每一位的操作，如果键的长度不确定（如变长字符串），基数排序服从就会显着下降，甚至不再适用。
[*]结构简单、按位可分解：键值最好是整数类型或可被转化为整型的值，便于拆解为各个“数字位”进行排序。
[*]容易天生且无需额外开销：如果为每个区块天生排序键的本钱过高，可能会抵消基数排序自己的上风。
因此，我们认为理论上通过合理的地面区块设计，确实有可能使基数排序成为最优选择。但具体能不能做到这一点，仍需要团结地面区块的现实数据结构与使用场景进行分析与实践验证。我们也要评估天生排序键的本钱是否划算，是否值得用基数排序替代其他传统的比力类排序。最终能否成为最优，还取决于权衡实现复杂度、运行服从和数据特性。
对的，这是有证实的，我几乎可以确定
我们在讨论排序算法的时间复杂度时，明确提到一个关键结论：对于通用数据的排序，排序算法的时间复杂度下限是 O(n log n)，也就是说，不存在一个通用的比力排序能在最坏环境下跑得比 O(n log n) 更快。这已经在理论上被数学证实过，是一种不可突破的边界。
这个结论适用于所有基于“比力”的排序算法，比如归并排序（merge sort）、快速排序（quick sort）、堆排序（heap sort）等，都是在这个理论下限附近运行的。
我们还提到“shell sort”（希尔排序），它并不是严格意义上的 O(n log n)，它的现实复杂度取决于具体的增量序列（gap sequence）。在某些环境下，它能跑得比 O(n log n) 更快一些，但在最坏环境下仍然达不到线性时间，因此在理论下限这件事上，它也不是例外。
我们之所以强调这一点，是为了明确排序算法在设计上的极限：如果想要突破 O(n log n)，就必须放弃“比力排序”这一门路，而选择其他类型的排序，比如基数排序（radix sort）、计数排序（counting sort）这类非比力排序算法。这些算法在特定条件下是可以达到 O(n) 时间复杂度的，但它们有条件要求，比如排序键必须是整数、固定大小、范围有限等。
因此，最终我们明确一点：在处置惩罚一样平常性、任意数据类型时，O(n log n) 是不可逾越的理论极限；只有在数据具备特定结构特性时，才可能使用 O(n) 的排序方法。我们在做体系设计时需要意识到这个根本限制，合理选择排序策略。
Shell sort 根本上就是带有可变跨度的冒泡排序吗？跨度每轮都变小？
我们提到了一种排序算法叫做 Shell Sort（希尔排序），它的本质可以被明白为一种改进版的冒泡排序（Bubble Sort），其重要特点是使用**可变跨度（gap）**来进行比力和互换。
在平凡的冒泡排序中，元素之间的比力和互换是逐个相邻地进行的，也就是说，我们每次比力的是相邻的两个元素（跨度为1），然后逐步把较大的值“冒泡”到右边，直到整个数组有序。
而在希尔排序中，我们不是一开始就比力相邻的元素，而是以一定的跨度（gap）来比力相距更远的两个值。比如我们可能一开始用跨度为5的方式进行比力，然后是3，末了是1。随着排序的进行，跨度渐渐缩小，最终退化为平凡的冒泡排序。这种做法的利益在于，它可以更早地把某些远距离放错位置的元素提前调解好，避免平凡冒泡排序那种服从极低的大量局部互换。
也就是说，希尔排序的核心思想是：先让数据初步有序（尤其是“全局”错位的元素），然后再逐步细化成完全有序。它通过可变跨度来控制比力范围，从而提高服从。虽然它并不是线性时间复杂度的排序算法，但比平凡的冒泡排序快得多，尤其是在处置惩罚大规模数组时服从提拔显着。
但要留意的是，希尔排序的现实性能很大程度上依赖于选择的“增量序列”（即跨度的厘革规律），不同的序列对应不同的时间复杂度。选得好的话，它可以在 O(n^1.3) 左右运行，选得不佳可能退化得很锋利。
总的来说，希尔排序可以被看作是一种通过“远距离比力”加快局部冒泡过程的策略，是对基础排序方法的一种高效改进，但它仍然没有打破 O(n log n) 的理论下限，也不是最优选择，只是在某些特定场景下性价比还不错。
黑板：Shell 排序教学
我们讨论了 Shell Sort（希尔排序） 的由来、原理以及它与冒泡排序的关系。
起首，希尔排序这个名字的来源并不清晰，不外通常认为它是以某位名叫 Shell 的人命名的。虽然具体细节可能不确定，但我们知道它就是叫这个名字。
接下来，我们将希尔排序的根本思想与冒泡排序进行了对比。冒泡排序的做法是：
[*]一次遍历中，我们比力每一对相邻的元素，例如第1个和第2个，第2个和第3个……如此往复；
[*]如果前面的元素比反面的元素大，就互换；
[*]这一过程重复进行，直到整个列表有序。
而希尔排序的不同点在于：
[*]它并不是从一开始就比力相邻的元素，而是选择一个“跨度”，比如先比力相隔5个元素的配对；
[*]第一轮可能比力第1个和第6个、第2个和第7个……这种“跨距离”的比力和互换；
[*]接着缩小跨度，比如从5变成3，然后再变成1，末了回归到传统冒泡的相邻比力；
[*]每一次缩小跨度都在不停让数据更趋于局部有序，直到整个序列排序完成。
这种方式的上风在于：可以更快地把那些“原来就距离正确位置很远”的元素移到正确方向上，从而减少后续细致比力时的工作量。
此外，我们还提到：
[*]希尔排序其实可以看作是一类排序算法的“家属”；
[*]它的具体表现取决于“增量序列”的设计（即每轮比力时所采用的跨度）；
[*]如果能根据数据的特点来设计这些跨度，排序服从会大幅提拔；
[*]理论上，这种方式可以避免传统冒泡排序中大量局部互换的题目。
虽然我们对某些细节记得可能不是特别精确，但团体明白是：希尔排序就是在冒泡排序的基础上加入了“远距比力”的优化机制，通过渐渐缩小间隔的方式，快速推动数据接近有序状态，再最终完成排序。这使得它在处置惩罚某些类型的数据时，性能远优于基础冒泡排序。
这个如今支持跨平台了吗？
我们目前讨论了关于是否“跨平台”的题目，团体可以总结如下：
目前项目还没有完全实现跨平台，因为当前开发重点集中在一个平台上，在该平台上完成开发之前，不会在其他平台上进行移植或测试。也就是说，我们的开发流程是先在一个平台上完成整个游戏，再思量扩展到其他平台。
不外，这并不意味着其他平台上完全无法运行。现实上，已经有其他人对项目进行了一些移植工作。具体来说：
[*]有人基于 SDL（Simple DirectMedia Layer） 做了一个移植版本；
[*]这个 SDL 版本的代码已经被上传到 GitHub 上；
[*]如果用户预购了游戏，就可以访问这个 GitHub 仓库；
[*]理论上，这个 SDL 移植版本是可用于跨平台开发的，比如在 Linux、Mac 等其他体系上运行；
[*]虽然我们没有亲自检察这个移植版本，但推测它应该是比力新的，有人在维护。
综上，目前我们官方只专注于一个平台，尚未完成多平台支持。但社区已有部分贡献实现了跨平台的能力，使用这些移植版本的代码，理论上可以在其他体系上运行和开发。是否使用这些版本，取决于开发者自己的需求与判定。
题外话：你更喜好 OpenGL 的固定功能 API，照旧可编程 API？我如今用的是现代方法，但固定管线那一套看起来逻辑更直观、流程更清晰
讨论了固定功能API与可编程API的题目。虽然现代的可编程方法被广泛使用，但从示例代码来看，固定管线的方式似乎更直观，明白流程也更容易。尽管如此，更倾向于使用可编程的方式，但也认为它在设计上仍有改进的空间。目前的可编程API有些混乱，因为它履历了许多阶段的发展，渐渐演变成如今的样子，像是经过不停厘革和重组后形成的一个复杂体系。
照你说的，稳定排序是不是会很耗资源？因为听起来可能会是最大 O(n² * logn)，要遍历数据两次？
讨论了稳定排序是否资源密集的题目。稳定排序的复杂度并不会是最大O(N²)，而是O(N log N)的，具体取决于排序的类型。例如，稳定的归并排序是一种有效的稳定排序算法，因为在执行过程中只会在必要时才互换元素。归并排序的实现方式使得它可以在不改变相对序次的环境下稳定排序，从而保证其稳定性。另一方面，冒泡排序也是稳定的，尽管它的时间复杂度为O(N²)，因此在数据量较大时服从较低。总结来说，稳定排序并不一定意味着必须使用更高的时间复杂度，像归并排序这种O(N log N)的稳定排序也是可以实现的。
你会故意留点 bug 给速通玩家去利用吗？
在讨论是否故意留下一些毛病给速通玩家时，表示并不会专门留下毛病供速通玩家用来破解游戏。现实上，游戏开发过程中几乎不可能做到完全没有毛病。纵然尽力避免，仍然会有一些bug存在。这些bug并不是故意留下的，而是在开发过程中天然会出现的。速通玩家会发现这些bug，并通过它们来破解游戏，这可能会成为一种有趣或搞笑的体验。因此，开发者并不会故意设计毛病，而是接受这些bug的存在，最终玩家会在游戏中发现它们并享受这种“粉碎”过程。
排序之后，是直接重写磁盘数据，照旧只是更新索引或指针？换句话说，排序后能否重新读到尾，照旧依旧得跳转读取？
排序操作的方式取决于具体的实现。在内存中进行排序时，通常环境下不需要对磁盘上的数据进行任何调解或重写，只是在内存中对数据进行操作。在某些环境下，排序过程中可能只是更新一些指针或者引用，而不是直接操作数据自己。举个例子，某些排序方法会使用引用表来排序，即通过排序数据的地点来间接访问数据。具体来说，数据自己并不会被直接移动或复制，而是通过对地点的排序来实现排序。如许，排序时现实上只是通过改变数据地点的序次来访问数据，避免了直接在内存中进行大量的复制操作。
这种方法通过引用或指针的间接方式，避免了需要在内存中频繁复制数据，从而提高了服从。因此，这种排序方法可以避免昂贵的数据复制操作，只是修改指向数据的引用或地点。
我是说你具体怎么解决这些题目的，这几周感觉就差临门一脚，然后又被“悬崖”卡住
我们不会公开讨论解决题目的具体方式，尤其是涉及到游戏引擎的实现。所有的游戏引擎代码是专有的，我们不会发布或讨论它是如何工作的。因此，博客中的内容重要是关于当前游戏的开发进展，讨论我们在开发过程中碰到的题目以及我们正在解决哪些题目，而不是具体的编程技能。虽然会有关于游戏的公告，先容游戏的相关信息，但这并不是一个编程技能博客，将来也不会涉及编程方面的讨论。所以，如果你期待在博客上看到有关编程的讨论，恐怕会失望，因为我们不会分享这类内容。
我前几天看到一篇文章说语法高亮对编程其实欠好，会让人只扫代码不明白，你同意吗？
有一篇文章提到语法高亮对于编程实践有害，认为它促进了“欣赏”而不是明白。对此，我觉得这是一种没有数据支持的主观见解，显得非常随意，根本无法证实如许的观点。所以我认为这看起来有些任意。但是，从个人经验来说，我自己通常会关闭许多语法高亮，甚至在我的代码中很少使用它。可能是因为我不太喜好别人通常使用的语法高亮方式。所以我觉得这应该是因人而异的，每个人的喜好不同。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]