本文共 1710 字，大约阅读时间需要 5 分钟。

QuickSort - 时间复杂度、空间复杂度及不稳定性分析

快速排序（Quick Sort）是造成现代内存排序算法性能提升的重要因素之一。它以平均时间复杂度 O(n log n) 而闻名，是目前被认为最好的比较类内排序算法。这种排序方法的核心优势在于其在处理无序数据时的平均效率，尤其是在数据分布接近随机的情况下，其性能尤为出色。

时间复杂度分析

快速排序的平均时间复杂度为 O(n log n)，这部分复杂度主要来自于递归调用的重复次数与数据规模之间的对数关系。具体演化来说，选择一个合适的将数据分成较小子集的支点，每次将数据分割为近似相等的两部分，这样分割操作的总次数限制了总的操作量。尽管在最坏情况下（如数据已排序或逆序），其时间复杂度可能升级至 O(n²)。但这种情况通常只出现在极端或特定数据排列下，对大多数实际应用而言，平均情况下的 O(n log n) 表现依然优越。

递归排序的另一个关键因素是 divide-and-conquer 原则，通过将问题分解为较小的子问题来解决。每次递归调用的数量取决于数据分割的大小，而分割的数目则与分割的递归深度有关。分割的深度大致为 log₂n，这也直接影响了排序的总操作次数，进而决定了时间复杂度。

空间复杂度分析

快速排序的空间复杂度为 O(log n)。这一复杂度来源于递归调用的调用栈，每一次递归调用都会在栈中记录当前处理的数据段信息。具体而言，选择一个支点并管理两个子区间的操作所需的额外空间随递归深度呈指数级增长，而递归深度本身为 log₂n，因此空间复杂度可被证明为 O(log n)。

该空间复杂度分析假设我们使用递归方法实现快速排序，并且处理中仅使用到常数额外的临时存储。每次递归处理一个子区间，仅在完成该区间后才释放所占用的临时存储，从而避免空间浪费。此外，考虑到较大的数据阶段，通常采用迭代方法或改进的方法来降低栈深度的影响，进一步优化了空间表现。

不稳定性分析

快速排序被归类为一类不稳定排序算法。其不稳定性体现在对处理相同键值时的排序结果可能变化。例如，假设有多于一个相同的键值存在，那么在排序过程中，这些值的相对顺序可能会发生改变。这种特性使得快速排序无法保证相同数据项的相对位置保持不变，这与稳定排序算法的预期结果相悖。

例子说明

take the following array as example: 4, 2, 1, 6, 3, 5, 3 随机选择 4 作为初始支点。比较 4 和 3 时，3 被移动到前面。对 4 和 6 的比较结果显示 4 小于 6，所以 6 被移动到数组的右边。在这一轮调整操作完成后，数组变为： 3, 1, 2, 4, 5, 3 这里可以看到，原有两个 3 的相对位置已经发生了变化，前一个 3 被移动到开头位置，后一个 3 被移动到中间位置。

这种现象很容易发生，因为快速排序的分割策略可能导致相同的键值被分配到不同的子区间中，并在多次重复的调整过程中，导致它们的相对位置发生变化。因此，快速排序不保证保持原有元素的相对顺序。

快速排序的工作原理

快速排序通过递归地选择一个支点（pivot），并将数据划分为左半部分和右半部分。这些部分再继续进行相同的分割和排序操作，直到每个子区间只包含一个元素。

adjust() 方法主要负责选择合适的 pivot，并将数组分割成左侧和右侧两个部分。通过比较 pivot 与数组末尾的元素，逐步将较大的元素移到目标位置，然后再将 pivot 放入当前的 low 位置。在比较过程中，如果当前的 low 从未超过 high，就开始考虑如何将右半部分的元素放置到 low 位置，以达到分割的目的。

在 compare 方法中，我们比较两个数的大小差异。结果为非负数时，表示 pivot 大于等于高位元素，此时可以停止比较并将高位元放到当前低位的位置。

[此处应包含文章中所展示的具体代码示例]

通过上述分析，可以清晰地看到快速排序时间复杂度和空间复杂度的来龙去脉，同时也理解了其作为不稳定排序算法的特性。这种对比分析有助于更好地把握快速排序的核心原理及其适应的应用场景。