排序算法概述：快速排序
排序算法概述：快速排序
发现一种最高效的排序算法
介绍
快速排序（Quicksort）可能是最流行的排序算法之一。在许多实验中，它表现出比其他排序方法（如归并排序或堆排序）更好的性能。
快速排序的基本思想是将数组递归地分成两部分：第一部分包含所有小于基准元素的元素，第二部分包含所有大于基准元素的元素。这个过程被称为分区。分区函数会在数组的两个划分部分上递归调用，直到只剩一个元素需要分区。
分区
首先，需要选择一个基准元素。这可以是数组中的任何元素。在我们的示例中，我们将选择数组的最后一个元素。然后，我们将通过循环遍历每个元素，将当前元素与基准进行比较。如果元素小于或等于基准，则将其保留在数组的左侧部分。否则，将元素移动到右侧部分。
首先，我们初始化两个指针：i 和 j。指针 j 指向第一个元素，而指针 i 指向 j 的前一个值 j – 1。通过引入变量 i 和 j，循环内满足以下不变式：
- 索引范围在 [left, i] 的元素小于或等于基准。
- 索引范围在 [i + 1, j) 的元素大于基准。
循环结束时，j 将等于 right，而索引 i 将把数组分成两部分。由于上述不变式的成立，我们的数组将被正确地分区。
在每次迭代中，j 增加 1，因此它始终指向当前元素。然后将当前元素 array[j] 与基准进行比较。如果元素小于或等于基准，则将其与位置为 i + 1 的元素交换位置。根据上述不变式，我们总是知道 array[i + 1] > 基准。因此，将小于或等于基准的元素与大于基准的元素进行交换，违反了不变式。为了保持不变式的正确性，需要将 i 增加 1。
如果 array[j] > 基准，则不变式仍然保持正确，我们只需进行下一次迭代（i 的值不变）。
很容易注意到，在所有迭代完成后，数组将被正确地分区。下面的代码片段演示了上述逻辑。请注意，返回基准元素的索引。
分区函数
排序
排序算法采用递归方式进行。首先，根据前一节的方法将数组分区成两部分。对于每个部分，再次递归调用分区过程，直到只剩一个元素需要分区。
以下是该算法的函数实现。
快速排序函数
复杂度
由于对快速排序的精确渐进证明涉及太多细节，相对较为复杂，因此我不打算详细讨论所有方面，而是提供非正式的证明。
在每次分区调用中，我们线性地遍历数组的所有元素，导致 O(K) 的复杂度，其中 K 是数组的大小。假设在每次分区过程后，基准元素将数组分成两个相等的部分，因此我们对它们都递归调用快速排序函数，直到只剩一个元素需要排序。这导致了与归并排序相同的函数调用结构。
唯一的区别是我们调用的不是合并函数，而是分割函数，但它们的时间复杂度都是O(K)。由于层级结构也是相同的，我们得出快速排序的时间复杂度是O(N * logN)。合并排序的渐近证明可以在这里找到。
排序算法，第一部分：合并排序
说到排序，合并排序是其中最受欢迎的算法之一。它基于著名的…
VoAGI.com
在上面的证明中，我们假设数组总是被平均分成两个相等的部分，这显然并不总是成立。假设分割过程总是只将一个元素与其他元素分开。这将导致每次迭代时数组大小分别为N – 1，N – 2，N – 3，…，1。让我们使用等差数列的求和公式计算这种情况下的总时间复杂度。
T(N) = O(N) + O(N – 1) + O(N – 2) + O(N – 3) + … + O(1) = O(N * (N + 1) / 2) = O(N²)
结果是时间复杂度为平方级别。这是快速排序的最坏情况。尽管如此，出现这种情况的概率非常小。
平均而言，快速排序的工作时间为O(N * logN)，并且优于其他排序算法。
想象一下，您开发了一个在底层使用快速排序算法的系统。总是选择一个主元素并不是一个好方法，根据相同的原则（在我们的例子中，我们一直选择数组的最后一个元素）。如果有人发现了选择主元素的策略，那么这个人可以明确地输入导致最坏分割情况和O(N²)时间复杂度的数组。这可能会显著降低系统的效率。这就是为什么最好在每次迭代中以不同的方式选择主元素。最流行的做法之一是随机选择主元素。
结论
我们已经学习了快速排序-一种著名的排序算法。尽管在最坏的情况下具有二次复杂度，但在实践中通常比其他算法（如合并排序或堆排序）表现更好，特别是对于大数组的情况。
除非另有说明，所有图片均由作者提供
