了解快速排序算法：分而治之

在计算机科学领域，QuickSort 是最高效、使用最广泛的排序算法之一。其对大数据集排序的惊人速度归功于其“分而治之”的策略。让我们来看看快速排序是如何工作的！

什么是快速排序？

QuickSort 是一种采用“分而治之”技术的排序算法。它选择一个称为主元的元素，并将列表划分为两个子数组：一个包含小于主元的元素，另一个包含大于主元的元素。该过程在这些子数组上递归重复，直到列表完全排序。

枢轴的选择可能会有所不同。一种简单的方法是选择列表中的第一个元素。 然而，根据具体情况，其他策略可能更有效。

快速排序步骤

1.递归停止准则

当列表有 0 或 1 个元素时，它已经排序，算法结束。

<code class="language-java">// Verifica se a lista tem 0 ou 1 elemento (já ordenada)
if (integerList.isEmpty() || integerList.size() == 1) {
    return integerList;
}</code>

2.列表分区：

下一步涉及选择一个主元并将列表分为两个子数组：一个具有较小的元素，另一个具有比主元大的元素。 请参阅如何完成此操作的示例：

<code class="language-java">int pivo = integerList.get(0); // Escolhendo o primeiro elemento como pivô
List<Integer> menores = new ArrayList<>();
List<Integer> maiores = new ArrayList<>();
for (int i = 1; i < integerList.size(); i++) {
   if (integerList.get(i) < pivo) {
      menores.add(integerList.get(i));
   } else {
      maiores.add(integerList.get(i));
   }
}</code>

注意： 请注意，比较从 i=1 开始，防止主元包含在次要子数组中。

3.递归：

递归开始发挥作用了！该算法将自己称为最小和最大子数组，重复该过程直到完成排序。结果的组合如下所示：

<code class="language-java">List<Integer> sorted = new ArrayList<>(quickSort(menores));
sorted.add(pivo);
sorted.addAll(quickSort(maiores));
return sorted;</code>

算法的复杂性

快速排序的渐近时间复杂度为 O(n log n)，表现出很高的效率，特别是与具有 O(n²) 复杂度的冒泡排序等算法相比。

注：此解释改编自 Aditya Bhargava 所著的《理解算法》一书的第 4 章。 应该注意的是，这里可能没有解决一些细微差别，建议您查阅其他来源以进行更深入的研究。

结论

QuickSort 是一种强大的算法，它使用递归来有效地对列表进行排序。与其他排序算法相比，它的主要属性是执行速度，特别是在长列表上。为了更全面的理解，建议阅读《理解算法》一书。

您在任何项目中使用过 QuickSort 吗？在评论中分享您的经验！

以上是了解快速排序算法：分而治之的详细内容。更多信息请关注PHP中文网其他相关文章！