C++ 中的摇晃排序

引言

排序方法在计算机科学领域至关重要，影响着数据分析、数据库管理系统以及诸如在计算机上整理文件等日常任务的方方面面。在可用的排序算法中，扫荡排序（Shaker Sort），也称为鸡尾酒排序（Cocktail Sort）或涟漪排序（Ripple Sort），就是其中一种。它对冒泡排序算法进行了改进。

扫荡排序的设计旨在克服冒泡排序的一个局限性，即即使在较大的元素已移动到正确位置后，每趟遍历仍需要遍历整个数组。通过结合比较和交换技术，扫荡排序通过从两端同时进行，优化了数组遍历，从而减少了比较和交换的次数。

本文将深入探讨扫荡排序的机制及其时间复杂度分析，并提供使用 C++ 实现的见解。我们将系统地解释该算法的运行方式，评估其性能特征，并与广泛使用的排序算法进行比较。此外，我们还提供了一个 C++ 扫荡排序的实现，供您集成到您的项目中或深入了解其功能。

排序方法在计算机科学中很重要，是解决问题的工具。理解这些算法的优缺点至关重要。无论您是学生、开发人员，还是热衷于拓宽知识领域的人，本文都将深入介绍扫荡排序及其在实际场景中的应用。

探索扫荡排序技术

• 过程始于一个无序的元素数组。
• 数组被分为两部分：一部分已排序，一部分未排序。
• 初始时，整个数组被认为是未排序的。
• 执行一系列双向遍历：从左到右，再从右到左。
• 在每次遍历中，比较相邻的元素，并在必要时进行交换。

从左到右遍历

• 从左到右进行。
• 比较相邻的元素。
• 如果左边的元素大于右边的元素，则交换它们。
• 一直进行到数组末尾。
• 最大的元素在已排序部分中向右移动。

从右到左遍历

• 改变方向，从右向左进行。
• 比较相邻的元素。
• 如果右边的元素比其左边的邻居小，则交换它们。
• 一直进行到数组开头。
• 最小的元素在未排序部分中向左移动。

缩小未排序的范围

• 在每次双向遍历之后，在两端各添加一个元素，以扩展已排序的范围。
• 结果是未排序的部分变小了。

停止条件

• 算法会持续进行双向遍历。
• 当一趟从左到右和从右到左的遍历都不需要交换时，算法就会停止。
• 这表明整个数组已排序。

主要优势

• 双向交换减少了不必要的比较和交换。
• 对于部分有序或包含少量逆序的数组非常有效。
• 您可以想象元素来回移动，就像被轻轻地推到位一样。

双向交换方法

• 扫荡排序与传统冒泡排序之间的关键区别。
• 涉及双向遍历数组：从左到右和从右到左。

从左到右遍历

• 从最左边的索引遍历到最右边的索引。
• 比较每对相邻的元素。
• 如果左边的元素大于右边的元素，则交换它们。
• 确保最大的元素“冒泡”到右端。

在扫荡排序中执行从右到左的遍历时

• 在完成从左到右的遍历后开始。
• 从最右边的索引遍历到最左边的索引。
• 比较元素，如果右边的元素小于左边的元素，则交换它们。
• 此过程确保最小的元素高效地向左端移动。

此方法的好处包括

• 减少不必要的比较和交换。
• 避免与已排序的元素进行冗余比较。
• 对于部分排序的数组或包含少量逆序的数组非常有效。

要可视化此过程

• 元素来回移动，就像被摇晃或涟漪一样。
• 较大的元素逐渐向右端移动，而较小的元素向左端移动。

随着此双向遍历的持续

• 已排序部分从两端开始，随着每次迭代而扩展。
• 未排序部分相应地缩小，直到在一次遍历中不再需要交换。

终止条件发生在

• 不需要任何交换，这表明整个数组已排序。

扫荡排序的效率在于其交换技术，使其在部分排序或逆序较少的数组上优于冒泡排序。

用 C++ 实现扫荡排序

输出

Unsorted array: 64 34 25 12 22 11 90 

Sorted array: 11 12 22 25 34 64 90

说明

1. 我们创建一个名为 shakeout 的函数，该函数接受对包含整数的 std::vector 的引用。

2. 最初，我们设置两个指针，left 和 right，分别指向数组的开头和结尾。

3. 此外，一个名为 swapped 的布尔变量被初始化，用于跟踪在迭代中是否发生了任何交换。

4. 主要循环将继续，只要 swapped 保持为 true，这表示发生了交换且数组未排序。

5. 在循环内部，我们开始进行一次向右扫描；

我们从左向右移动。1，同时比较元素。

如果左边的元素大于右边的元素，我们交换它们。将 swapped 设置为 true。

进行此遍历后，我们将 right 的值减一，以排除末尾的元素不受后续比较的影响。

6. 随后，我们进行一次从右向左的扫描；

我们从右向左+1进行遍历，同时按顺序比较元素。

当遇到右边元素小于其对应元素的情况时，我们交换它们并相应地更新 swapped。在遍历期间，我们将 right 指针向左移动，以便在下次遍历时排除已排序的元素。

7. 该过程将持续进行，直到一次遍历中不再发生交换，这表明数组已按顺序排列。

此方法基于扫荡排序算法，该算法涉及双向移动，在元素顺序不正确时交换它们，并逐渐从两端缩小数组的范围。

扫荡排序的优点

1. 对部分有序数组有效：扫荡排序在处理部分排序或元素顺序错误的数组时效率很高。通过在从左到右和从右到左的遍历之间切换，它可以最大限度地减少比较和交换。
2. 性能优于冒泡排序：尽管与冒泡排序具有相同的时间复杂度 (O(n²))，但扫荡排序由于其双向交换技术，通常在实际场景中表现更好，该技术减少了必要的比较和交换次数。
3. 响应性：扫荡排序是一种利用输入数组的有序性来减少所需比较和交换次数的算法。
4. 内存效率高：扫荡排序是一种原地排序算法，它在不占用与输入数组大小相等的额外内存的情况下对数组进行排序。
5. 易于实现：该算法非常容易理解和应用，是注重简洁性的情况下的一个不错的选择。

扫荡排序的缺点

1. 处理大型无序数组的挑战：虽然扫荡排序在处理有序数组时表现良好，但当处理大型、高度无序的数组时，其效率会显着下降。在这种情况下，选择快速排序或归并排序等更有效的排序方法会更有益。
2. 最坏情况时间复杂度不佳：与冒泡排序一样，扫荡排序的最坏情况时间复杂度为 O(n²)，这使得对缺乏组织的数据集进行排序效率低下。
3. 仍有交换：尽管采用了双向方法，但当元素已在其正确位置时，扫荡排序仍然会进行交换，尽管比冒泡排序的次数少。
4. 不适用于排序链表：扫荡排序是为数组设计的，不适用于排序链表，因为它需要通过索引访问元素。
5. 缺乏并行处理的适应性：扫荡排序不易适应并行处理，因此与归并排序或基数排序等算法相比，在并行处理环境中不太理想。

总之，扫荡排序是组织部分排序或只有少量混乱的数组的好选择。然而，对于大型、高度无序的数组或时间效率至关重要的场景，它可能不是理想的解决方案。其简单的过程和在内存空间内工作的能力使其在学习目的或内存限制是一个考虑因素时非常有用。