C++ 快速排序算法

快速排序算法简介

在计算机科学和数据处理中，排序是一项基本操作。它包括将一组对象或组件按特定顺序排列，通常是根据某个标准，以升序或降序排列。数据库、搜索引擎和信息检索等应用程序都依赖于排序。

快速排序算法

一种有效且流行的基于比较的排序算法是快速排序，有时也称为交换排序。它由 Tony Hoare 于 1960 年发明，此后已成为一种常见的排序技术。快速排序的速度广为人知，尤其对于大型数据集而言，它经常被用作其他排序算法的标准。

快速排序的核心思想是将数据集划分为更小的子问题，独立地对每个子问题进行排序，然后合并已排序的子问题以获得最终的已排序数据集。该过程使用分治策略来完成。快速排序使用的数据集划分过程是其主要活动。

分区步骤

分区步骤是快速排序算法的核心。其工作原理如下：

1. 从数据集中选择一个枢轴元素。可以选择枢轴元素的不同方法，枢轴的选择会影响算法的性能。
2. 重新排列数据集中的元素，使得左边的所有元素都大于枢轴，而右边的所有元素都小于枢轴。现在，枢轴元素位于排序的最后位置。
3. 递归地将分区步骤应用于枢轴左右两侧的子数组，直到数据被排序。

选择枢轴

使用的枢轴元素和分区技术对快速排序的效率有重大影响。有几种选择枢轴的方法，例如：

选择第一个元素作为枢轴：在此简单方法中，数据集的第一个元素始终被选为枢轴。

选择最后一个元素作为枢轴：与前一种方法类似，但选择最后一个元素作为枢轴。

选择三数取中：此技术选择数据集的第一个、中间和最后一个元素的中间值作为枢轴。它旨在减少遇到最坏情况的可能性。

随机选择枢轴：在此方法中，枢轴是从数据集中随机选择的。这可以降低发生最坏情况事件的风险。

快速排序的算法步骤

1. 选择一个枢轴元素

• 从列表中选择一个枢轴元素。算法的有效性可能会受到枢轴选择的影响。第一个元素、最后一个元素、中间元素或随机元素是常见的枢轴选择程序的示例。

2. 分区数组

• 重新排列数组的元素，使所有小于枢轴的元素都移到其左侧，而所有大于枢轴的元素都移到其右侧。
• 枢轴元素现在已被排序到其最后一个位置。

3. 递归排序子数组

• 对枢轴左侧的子数组（包含小于枢轴的元素）递归应用快速排序算法。
• 对枢轴右侧的子数组（包含大于枢轴的元素）递归应用快速排序算法。

4. 合并已排序的子数组

一旦所有递归调用完成，整个数组就已排序，因为每个枢轴元素都处于正确的位置。

5. 重复直到整个数组被排序

当整个数组被排序时，再次重复选择枢轴、划分数组和递归排序子数组的步骤。

以下是快速排序算法的伪代码表示

此伪代码描述了快速排序算法的两个主要阶段：分区过程和子数组的递归排序。该方法会一直重复，直到整个数组被排序，每个枢轴元素都处于正确的位置。

C++ 快速排序实现

在我们熟悉了快速排序算法的基础知识之后，现在让我们来看一下 C++ 实现。我们将首先实现分区阶段，然后是递归排序过程。

说明

在 C++ 实现中，我们定义了三个函数：

• 'Partition'：此函数接受一个向量 'arr' 和两个整数参数 'low' 和 'high'，它们定义了要分区的元素的范围。它选择第一个元素作为枢轴，并颠倒向量元素的顺序，使得枢轴左边的所有元素都大于右边的所有元素。返回枢轴元素的索引。
• 'quickSort'：此排序函数主要实现了快速排序方法。向量 'arr' 和索引 'low' 和 'high' 指定了要排序的元素范围。直到整个数组被排序，它都会递归地划分数组并对左右子数组进行排序。
• 'printArray'：此函数用于打印数组的元素。
• 在 'main' 函数中，我们展示了如何使用 'quickSort' 函数对示例数字向量进行排序。在打印原始数组之后，使用快速排序方法对数组进行排序，然后打印。

输出

Original Array: 12 4 5 6 7 3 1 15 
Sorted Array: 1 3 4 5 6 7 12 15

性能分析

在普通和理想情况下，快速排序都以其出色的性能而闻名。然而，当枢轴选择经常导致不平衡的分区时，其最坏情况时间复杂度为 O(n²)。通常采用三数取中或随机枢轴选择程序来降低这种风险。

其中 'n' 是要排序的元素数量，快速排序的平均和最佳情况时间复杂度为 O(n*log(n))。特别是对于大型数据集，这使其成为最快的排序方法之一。此外，由于快速排序是一种原地排序算法，因此无需额外的 RAM 来存储已排序的数据。

递归函数调用和调用栈所需的空间由快速排序的空间复杂度 O(log(n)) 表示。总的来说，这种空间复杂度非常有效，这使得快速排序能够用于排序大型数据集。

一些实际用例

1. 排序大型数据库：在数据库管理系统中，快速排序常用于高效地对大量数据进行排序。
2. 搜索算法：当数据需要在搜索之前进行排序时，它会被用于二分查找等搜索方法。
3. 数值分析：对于对数值数据进行排序，快速排序被用于科学计算和数值分析。
4. 文件系统：快速排序是一个不错的选择，因为文件系统经常需要快速地组织和检索数据。

C++ 中快速排序算法的优点和缺点

快速排序是一种高效快速的排序算法，得到了广泛应用。由于其诸多优点，它成为各种应用中排序的热门选择。然而，与所有算法一样，它也有一些缺点和限制。在本文中，我们将探讨 C++ 中快速排序的优点和缺点，以帮助您理解何时以及为何使用它。

快速排序的优点

1. 高效率：快速排序的出色效率尤其适合大型数据集。其平均时间复杂度为 O(n*log(n))，这比冒泡排序和插入排序等许多其他排序算法都要快。在性能至关重要的情况下，这种效率是一个显著优势。
2. 原地排序：作为一种原地排序方法，快速排序在排序数据时无需额外的内存或存储空间。在内存有限的情况下，在提供的数组本身中排序元素可能很重要。
3. 缓存友好：快速排序的算法设计通常会导致出色的缓存性能。它具有很强的局部性引用，在访问数据片段时可以减少缓存未命，从而加快处理速度。
4. 枢轴选择的灵活性：快速排序的可配置枢轴元素选择使程序员能够根据自己的特定需求定制算法。当枢轴选择算法经过修改以优化各种输入数据类型的性能时，发生最坏情况的可能性会降低。

最后和第一个枢轴选择：初始和最终枢轴。这些策略简单易用。它们选择分别使用第一个或最后一个元素作为枢轴。

三数取中枢轴：此技术选择数据集的第一个、中间和最后一个元素的中间值作为枢轴。这可以降低最坏情况的风险。

随机枢轴选择：通过使用随机元素作为枢轴，该方法变得不那么可预测，并且更能抵抗恶意输入数据。

5. 并行化潜力：快速排序可以有效地并行化，使其能够受益于分布式计算环境和多核计算机。这使得能够并发排序非常大的数据集，从而极大地提高了其性能。
6. 广泛使用：快速排序是一种成熟且流行的排序算法。由于其有效性和速度，它经常被用作计算机语言和库中的默认排序技术。因此，开发人员通常熟悉其实现和行为。

快速排序的缺点

1. 最坏情况时间复杂度：快速排序的最坏情况时间复杂度是其主要缺点之一。在最坏的情况下，当枢轴选择持续导致不平衡的分区时（例如，通过始终选择最小或最大的元素作为枢轴），快速排序可能会下降到 O(n²)，其中 'n' 是要排序的项目数。在某些情况下，这种最坏情况可能是一个严重的缺点。
2. 对枢轴选择的敏感性：选择的枢轴元素将对快速排序的性能产生重大影响。尽管存在减轻这种敏感性的枢轴选择方法，但糟糕的枢轴选择可能会导致性能不佳甚至出现最坏情况。
3. 缺乏稳定性：快速排序是一种不稳定的排序算法。当两个元素具有相同的键时，排序的稳定性意味着在已排序输出中的相对顺序与初始输入中的相对顺序保持不变。尽管在某些应用中可能很重要，但快速排序不能保证稳定性。
4. 递归性质：虽然可以通过使用尾递归或迭代技术来解决此问题，但它会增加解决方案的复杂性，并且在排序非常大的数据集时可能导致堆栈溢出问题。
5. 非自适应：由于快速排序不是一种自适应排序算法，因此排序部分已排序的数据并不会大大提高其性能。当给定部分排序的输入时，某些排序算法（如插入排序）表现更好。
6. 不适用于链表：快速排序不是排序链表的最有效方法。由于它依赖于对元素的随机访问，因此它不能充分利用链表数据结构，这可能导致性能不佳，而与合并排序或插入排序等其他排序算法相比。

结论

在计算机科学和各种应用中，快速排序是一种灵活且非常有效的排序算法。由于其速度、原地特性和多功能性，它是排序大型数据集的热门选择。尽管它可能具有 O(n²) 的最坏情况时间复杂度，但在实践中，可以通过使用适当的枢轴选择技术来缓解此问题。正确使用时，快速排序的性能优于许多其他排序算法，并且在计算机科学和数据处理领域至关重要。