循环排序算法 | Baeldung 关于计算机科学

1. 简介

循环排序是一种就地、基于比较的排序算法，以最小化写入次数而闻名。 与传统的排序算法（如快速排序和归并排序）不同，循环排序以尽可能少的交换次数重新排列元素。因此，当写入操作代价高昂时，它尤其有效，例如在电可擦除可编程只读存储器 (EEPROM) 或闪存中。

在本教程中，我们将解释循环排序的工作原理，并提供该算法的逐步伪代码实现。然后，我们将探讨其时间和空间复杂度，并讨论循环排序特别有用的用例。我们将把循环排序与其他排序算法进行比较，以便全面了解。

2. 循环排序的工作原理

循环排序通过计算小于它的元素的个数将每个元素放置在其正确的位置。如果一个元素不在其正确的位置，我们将它移动到合适的索引，这个过程将持续到整个数组排序完成

algorithm CycleSort(array, n):
    // INPUT
    //    array = unsorted array (0-indexed)
    //    n = array size
    // OUTPUT
    //    Sorted array (in-place)

    for cycle_start from 0 to n - 2:
        item <- array[cycle_start]
        position <- cycle_start

        // Step 1: Find the correct position
        for i from cycle_start + 1 to n - 1:
            if array[i] < item:
                position <- position + 1

        // Skip if the item is already in the correct place
        if position = cycle_start:
            continue

        // Handle possible duplicates
        while item = array[position]:
            position <- position + 1

        
        // Step 2: Place the item in the correct position
        // (swap means exchanging 'item' with array[position], not array[cycle_start])
        swap(array[position], item)

        // Step 3: Rotate the rest of the cycle
        while position != cycle_start do:
            position <- cycle_start
            for i from cycle_start + 1 to n - 1 do:
                if array[i] < item:
                    position <- position + 1
            while item = array[position]:
                position <- position + 1
            swap(array[position], item)

在循环排序中，一个“循环”指的是当一个元素放置错误时触发的一系列交换。每个循环形成一个闭环，将错位元素移动到其正确的位置，直到原始起始元素返回其初始索引。

2.1. 循环排序的迭代

正如我们所见，循环排序的迭代包含三个步骤

在步骤 1 中，我们通过计算小于当前元素的个数来找到当前元素的确切位置，以确定它在最终排序数组中的位置。如果该位置已经被重复项占据，我们将向右移动直到遇到不同的元素。

在步骤 2 中，我们将项目（保存在临时变量中）放置在步骤 1 中找到的位置，通过将其与 array[position] 的值交换。 被置换的值成为新的项目，继续循环。这不涉及直接交换 array[cycle_start] 与 array[position]，除非项目已经返回到原始位置。

在步骤 3 中，我们遍历循环的其余部分。 将项目放置在其正确的位置可能会从数组中置换另一个值。我们通过对每个被置换的项目重复相同的过程（找到正确的位置、处理重复项和交换），直到原始项目返回其起始位置来解决这个问题。这种旋转确保循环中的所有元素都以最小的数据移动被正确放置。

3. 示例

让我们逐步了解循环排序如何对未排序数组 [30, 10, 20, 50, 40] 进行操作。为了清楚起见，我们水平显示外循环的每次迭代。我们用蓝色突出显示数组中需要交换和在一次循环中移动的元素

现在，让我们逐步检查循环排序的每个迭代，用于未排序数组 [30, 10, 20, 50, 40]。

我们从 cycle_start = 0 开始，当前元素为 30，存储在临时变量 item 中。在步骤 1 中，我们找到该元素的确切位置。通过计算小于 30 的元素数量，我们发现有 2 个这样的元素，这告诉我们 30 应该放在索引 2 上。由于数组中没有 30 的重复项，我们不需要进一步调整目标位置。在步骤 2 中，我们将 item 30 放在索引 2 上，取代了 20，后者成为新的 item。在步骤 3 中，我们继续循环。我们将 item 20 放在索引 1 上，取代了 10，后者成为下一个 item。最后，我们将 item 10 放在索引 0 上，将原始值 30 移回其起始位置，从而完成循环。

接下来，cycle_start = 1，当前元素是 20。它位于正确的位置，cycle_start = 2 和 30 也是如此。

继续到 cycle_start = 3，我们关注元素 50。在步骤 1 中，我们计算小于 50 的元素数量，包括 10、20、30 和 40 — 共四个。这意味着 50 应该放在索引 4 上。同样，没有重复项，所以在步骤 2 中，我们将 item 50 放在索引 4 上，取代了 40，后者成为新的 item。在步骤 3 中，我们继续循环，将 item 40 放在索引 3 上，从而将 40 放在起始索引上，完成循环。

没有更多元素需要处理，循环排序完成。最终排序后的数组是 [10, 20, 30, 40, 50]。

4. 时间和空间复杂度分析

从时间复杂度的角度来看，循环排序在最好、平均和最坏情况下均为 $O(n^2)$ 。 这是因为该算法可能会将每个元素与其他元素进行比较，以确定其在数组中的正确位置。

尽管具有二次运行时间，但循环排序的特点是执行的写入次数很少。该算法旨在执行最少数量的写入操作，具体来说，对于 $n$ 个元素，写入次数为 $\O(n)$ 。 原因如下：

每个元素最多移动一次到其最终排序位置。
对于长度为 k 的循环（需要旋转到位的一系列元素），该算法执行恰好 k-1 次写入来解决循环。
对数组中的所有循环求和，总的交换次数等于元素数量减去循环数量。由于所有循环的总长度不能超过 n，因此总交换次数为 $\leq n$ 。因此，写入次数为 $O(n)$ 。

在空间方面，循环排序非常高效。它原地操作，不需要额外的内存，从而导致辅助空间复杂度为 $O(1)$ 。 这在必须将内存开销保持在最低限度的系统中尤其重要。

5. 何时使用循环排序

由于其二次时间复杂度，循环排序并非通用排序算法。但是，当写入操作昂贵或受限时，它很有用。 这使其在嵌入式系统、固件应用程序和内存受限的环境中非常有效。

该算法在排序包含不同元素的数组时效果最佳。在这种情况下，循环结构更简单且更有效地遍历。相反，循环排序不太适合包含许多重复值的数据集，因为管理重复项需要额外的检查以避免冗余循环，这可能会使实现复杂化并降低其有效性。

同样，当处理大型数据集时，循环排序变得不切实际。 $O(n^2)$ 时间复杂度使排序数十万或数百万个元素效率低下。在这些情况下，更快的算法，如合并排序或快速排序更合适。

6. 循环排序与其他排序算法的比较

与保证最坏情况复杂度为 $O(n \log n)$ 的合并排序或平均时间复杂度为 $O(n \log n)$ 的快速排序不同，循环排序在最好和最坏情况下都是 $O(n^2)$ 。但是，循环排序显著减少了写入操作（交换）的数量

算法	比较（最坏情况）	交换/写入（最坏情况）	总计（比较 + 交换）
循环排序	$O(n^2)$	$O(n)$	$O(n^2)$
快速排序	$O(n^2)$	$O(n^2)$	$O(n^2)$
合并排序	$O(n\log(n))$	$O(n\log(n))$	$O(n\log(n))$
堆排序	$O(n\log(n))$	$O(n\log(n))$	$O(n\log(n))$
插入排序	$O(n^2)$	$O(n^2)$	$O(n^2)$

大多数排序算法，例如插入排序、堆排序，甚至快速排序，由于重复的交换或递归调用，涉及大量的写操作。相比之下，循环排序（Cycle Sort）直接将每个元素写入其最终位置，冗余最小。

然而，循环排序（Cycle Sort）不是一个稳定的排序算法，这意味着相等元素的相对顺序可能不会被保留。在处理具有多个字段的结构化数据时，稳定性通常是期望的，因此也必须考虑这个限制。

7. 结论

在本文中，我们讨论了循环排序（Cycle Sort）。

循环排序（Cycle Sort）是一种内存高效的排序算法，在最小化写操作至关重要的环境中表现出色。虽然其时间复杂度是二次方的，但其写效率是最佳的。它不适合通用用途，但在希望写操作（交换）次数尽可能低的专用硬件和受限系统中，它具有价值。

核心概念

操作系统

神经网络

图论

LaTeX

完整存档

关于 Baeldung