目录
1️⃣：时间成本 (Cost in Time) -> 时间复杂度 (Time Complexity)
2️⃣：空间成本 (Cost in Space) -> 空间复杂度 (Space Complexity)
3️⃣：结果的品质 (Quality of the Result) -> 稳定性 (Stability)
我们面临的根本问题是什么？
我们的起点是：有一个无序的集合，我们的目标是得到一个有序的集合。
为了实现这个目标，我们可以想出很多种不同的方法（也就是算法 (Algorithm)）。既然有多种方法，一个根本性的问题就出现了：我们如何判断哪种方法更好？
“更好”是一个模糊的词。为了让它变得可以衡量，我们需要把它分解成具体的、可量化的指标。
这就好比评价一辆车，我们会从“速度有多快？”、“耗油多少？”、“是否平稳？”这些具体的维度去分析，而不是笼统地说“这是一辆好车”。
对于算法，我们同样需要找到这些关键的评判维度。让我们从最朴素、最符合直觉的“成本”观念开始。
1️⃣：时间成本 (Cost in Time) -> 时间复杂度 (Time Complexity)
任何一个方法都需要花费时间来完成。这是我们最关心的成本。
第一步：如何衡量“时间”？
我们可以用秒表来计时吗？不行❌。原因很简单：
在我的旧电脑上运行10秒的算法，在你的新电脑上可能只需要1秒。
用C++写的程序和用Python写的同一个算法，运行时间也不同。
算法处理10个数据和处理1000万个数据，时间天差地别。
所以，用物理时间（秒、毫秒）来衡量算法本身的好坏是不公平、不科学的。我们需要一种与具体机器、具体语言无关的，能够描述算法内在效率的衡量方式。
第二步：抽象“时间”为“操作次数”
让我们回到计算机工作的本质。无论多么复杂的程序，最终都会被分解成CPU执行的一系列基础操作。在排序这个任务中，最核心、最频繁的操作是什么？
比较 (Comparison)：
if (a > b)—— 这是判断元素顺序的基础。移动 (Movement) / 交换 (Swap)：
temp = a; a = b; b = temp;—— 这是将元素放到正确位置的基础。
💡一个算法所花费的时间，主要就消耗在执行这些基础操作上。因此，一个绝妙的想法诞生了：
我们可以通过计算一个算法完成任务所需要的“基础操作总次数”来衡量它的时间成本。 这个总次数与具体的机器无关，它只与算法的逻辑和数据的规模有关。
第三步：关联“操作次数”与“数据规模”
操作总次数并不是一个固定的数字，它显然与我们要处理的数据量有关。我们用一个字母 n 来表示数据集合中元素的数量（数据规模）。
📊现在，我们的目标变成了：找到一个函数 f(n)，它能表示出当数据规模为 n 时，算法需要执行的基础操作次数。例如，某个算法可能需要 f(n) = 2n^2 + 5n + 7 次操作。
第四步：关注“增长趋势”，忽略细节
我们真的需要上面那个如此精确的函数 f(n) = 2n^2 + 5n + 7 吗？
设想一下，当 n 变得非常巨大时（比如一百万），n^2 这一项的值将远远超过 n 和常数7。2n^2 和 5n 相比，后者几乎可以忽略不计。
📌在算法分析中，我们最关心的是当数据规模趋于无穷大时，操作次数的增长趋势和级别。
是像 n (线性) 一样增长，还是像 n^2 (平方) 一样增长，或是像 log n (对数) 一样增长？
✅ 为了描述这种趋势，我们引入了大O表示法 (Big O Notation)。它做两件事：
只保留函数中对增长趋势影响最大的项（最高阶的项）。
忽略这一项的常数系数。
所以，对于 f(n) = 2n^2 + 5n + 7，我们将其时间复杂度记为：O(n^2)
这就是时间复杂度的由来。它回答了最开始的那个问题“算法有多快？”，
但用一种更本质、更科学的方式来回答：“算法的执行耗时随着数据规模的增长而如何增长？”
第五步：考虑不同输入状况
对于同一个规模n，算法的“运气”也可能不同。
最坏情况 (Worst Case): 输入的数据恰好让算法执行了最多的操作次数。
最好情况 (Best Case): 输入的数据恰好让算法执行了最少的操作次数。
平均情况 (Average Case): 在所有可能的输入下，算法的期望操作次数。
我们通常最关注最坏情况时间复杂度，因为它为算法的性能提供了一个“下限保证”。无论输入数据多么糟糕，算法的运行时间都不会超过这个量级。
2️⃣：空间成本 (Cost in Space) -> 空间复杂度 (Space Complexity)
除了时间，算法运行还需要消耗另一种宝贵的资源：内存。
第一步：如何衡量“空间”？
和时间一样，我们不关心算法用了多少个字节（bytes），因为这和数据类型、编译器有关。
我们关心的是：为了完成排序，算法需要额外申请多少内存空间？
🔑这里的“额外”是关键。输入数据本身（比如那个包含n个整数的数组）占用的空间是必须的，我们不把它算在算法的“成本”里。我们只计算那些为了实现算法逻辑而临时使用的辅助空间。
第二步：关联“额外空间”与“数据规模”
我们提出的问题是：这个额外空间的需求，是否会随着数据规模 n 的增长而增长？
情况A： 某个算法从头到尾只需要几个临时变量（比如用于循环的 i、j，用于交换的 temp）。
无论 n 是10还是一千万，需要的临时变量都是这几个。这种与n无关的、恒定的额外空间需求，我们称之为常数空间复杂度，记为：O(1)
✅ 这种算法通常被称为原地算法 (In-place Algorithm)。
情况B： 某个算法可能需要创建一个与原始数组同样大小的临时数组来辅助排序。那么它需要的额外空间就和 n 成正比。我们称之为线性空间复杂度，记为：O(n)
这就是空间复杂度的由来。它回答了另一个核心成本问题：“为了运行这个算法，我需要付出多大的额外内存代价？”
3️⃣：结果的品质 (Quality of the Result) -> 稳定性 (Stability)
分析完“时间”和“空间”这两个核心“成本”后，我们还需要考虑一个与“品质”相关的问题。排序的最终结果都是有序的，但有序的集合之间是否存在细微的、但很重要的差别？
第一步：发现问题——当元素不唯一时
如果我们要排序的只是一串唯一的数字，比如 [3, 1, 2]，那么排序结果必然是 [1, 2, 3]，所有算法的结果都一样。
但如果数据包含重复的值呢？比如，[3, 5, 2, 3]。 排序后的结果是 [2, 3, 3, 5]。但是，这两个 3 的顺序呢？
为了区分它们，我们给它们做个标记：[3a, 5, 2, 3b] (这里的 a 和 b 只是为了我们的观察，它们的值都是3)。 排序后，可能出现两种结果：
[2, 3a, 3b, 5][2, 3b, 3a, 5]
在第一种结果中，3a 原本就在 3b 的前面，排序后依然在前面。它们的原始相对顺序得到了保持。 在第二种结果中，它们的相对顺序被颠倒了。
第二步：定义“稳定性”
这个“是否保持相等元素原始相对顺序”的特性，就是一个非常重要的品质衡量标准。我们将其定义为稳定性 (Stability)。
如果一个排序算法能保证总是产生第一种结果，我们称之为稳定排序 (Stable Sort)。
如果它可能产生第二种结果，我们称之为不稳定排序 (Unstable Sort)。
第三步：为什么稳定性很重要？
在只对数字排序时，它似乎不重要。但想象一下，你在为一个电子表格排序。表格里有“姓名”和“入学年份”两列。
你首先点击“入学年份”列头，对所有学生按年份排序。
然后，你再点击“姓名”列头，对所有学生按姓名排序。
如果你用的姓名排序算法是稳定的，那么排序后，同姓的学生（比如好几个姓“王”的）会自然地按照入学年份的早晚排列。
但如果算法是不稳定的，那么这些姓“王”的学生的年份顺序就可能被打乱，你第一次排序的成果就被破坏了。
这就是稳定性的由来。它不衡量效率成本，而是衡量算法行为的一种正确性和可预测性，在处理复杂数据时至关重要。
结论
我们从“如何评价一个方法的好坏？”这个最根本的问题出发，一步步推导出了分析排序算法的三个核心标准：
时间复杂度：回答了“时间成本”问题，衡量算法执行时间随数据规模的增长趋势。
空间复杂度：回答了“资源成本”问题，衡量算法需要多少额外的内存空间。
稳定性：回答了“结果品质”问题，衡量算法在处理相等元素时的行为是否可预测。
这三个标准共同构成了一个完整的框架，使我们能够对任何排序算法进行深入、公平、全面的分析和比较。