Cycle Sort 算法

在本文中，我们将讨论 Cycle Sort 算法。Cycle sort 是一种比较排序算法，它将数组分解为若干个循环，每个循环都可以旋转以产生一个排序后的数组。从理论上讲，它在减少写入原始数组的次数方面是最佳的。

它是一种原地且不稳定的排序算法。Cycle sort 将数组分解为若干个循环，每个循环中的元素都可以旋转以产生一个排序后的数组。Cycle sort 的时间复杂度为 O(n²)，即使在最佳情况下也是如此。

现在，让我们看一下 Cycle sort 的算法。

算法

假设有一个包含 n 个不同元素的数组 arr。给定一个元素 A，我们可以通过计算小于 A 的元素的数量来找到它的索引。

1. 如果元素在其正确的位置，只需保持原样。
2. 否则，我们需要通过计算小于它的元素的数量来找到 A 的正确位置。另一个元素 B 被替换以移动到其正确的位置。这个过程一直持续到我们找到一个元素位于 A 的原始位置。

上述过程构成了一个循环。重复这个过程来处理列表中的每个元素，直到列表被排序。

Cycle Sort 算法的工作原理

现在，让我们看看 Cycle Sort 算法的工作原理。为了理解 Cycle sort 算法的工作原理，让我们取一个未排序的数组。

设数组的元素为 - {30, 20, 10, 40, 60, 50}

现在，给定的数组已完全排序。

Cycle Sort 复杂度

现在，让我们看看 Cycle Sort 在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将查看 Cycle Sort 的空间复杂度。

1. 时间复杂度

Cycle Sort 在所有三种情况下的时间复杂度均为 O(n²)。即使在最佳情况下，它也需要 O(n²) 的时间来对数组元素进行排序。在 Cycle Sort 中，总是需要从当前位置遍历整个子数组，以计算小于当前元素的元素数量。

因此，在 Cycle Sort 中，给定的数组是已经排序还是未排序并不重要。它对算法的运行时间没有影响。因此，Cycle Sort 必须以二次时间运行。

2. 空间复杂度

• Cycle Sort 的空间复杂度为 O(1)。

Cycle Sort 实现

现在，让我们看看不同编程语言中的 Cycle Sort 程序。

程序：用 C 语言实现 Cycle Sort 的程序。

输出

程序：用 C++ 实现 Cycle Sort 的程序。

输出

程序：用 C# 实现 Cycle Sort 的程序。

输出

执行上述代码后，输出将是 -

程序：用 Java 实现 Cycle Sort 的程序。

输出

执行上述代码后，输出将是 -

这就是本文的全部内容。希望本文能为您提供帮助和信息。