循环排序算法

Question

我在浏览互联网时发现有一种称为循环排序的算法，它可以使内存写入次数最少。但是我无法在任何地方找到该算法。如何检测一个循环中是否存在循环大批？ 谁能给这个算法完整的解释？

Answer 1

循环排序算法的动机是循环分解 。循环分解最好通过示例来解释。假设您有这个数组：

4 3 0 1 2

假设我们有这个已排序的序列，如下所示：

0 1 2 3 4

我们如何对这个已排序的数组进行洗牌才能得到洗牌后的版本？好吧，让我们将它们并排放置：

0 1 2 3 4
4 3 0 1 2

让我们从头开始。请注意，数字 0 被交换到最初由 2 持有的位置。数字 2 又被交换到最初由 4 持有的位置。最后，数字 4 被交换到最初由 0 持有的位置。换句话说，元素 0、2 和 4 均向前循环一位。这就留下了数字 1 和 3。请注意，1 交换到 3 所在的位置，3 交换到 1 所在的位置。换句话说，元素 1 和 3 向前循环一个位置。

根据上述观察，我们可以说序列 4 3 0 1 2 具有循环分解 (0 2 4)(1 3)。这里，括号中的每组术语的意思是“向前循环这些元素”。这意味着将 0 循环到 2 所在的位置，将 2 循环到 4 所在的位置，将 4 循环到 0 所在的位置，然后将 1 循环到 3 所在的位置，将 3 循环到 1 所在的位置。

如果您对特定数组进行循环分解，则可以按排序顺序将其返回，只需将所有内容向后循环一个位置即可实现最少的写入次数。 循环排序背后的想法是尝试确定输入数组的循环分解是什么，然后反转它，将所有东西放回原位。

这样做的部分挑战是弄清楚所有东西最初所属的位置，因为循环分解假设您知道这一点。通常，循环排序的工作原理是查找每个元素并计算有多少个元素小于该元素。这是昂贵的 - 它会影响排序算法的 Θ(n²) 运行时间 - 但不需要任何写入。

Answer 2

如果有人需要的话，这里有一个 python 实现

def cycleSort(vector):
    writes = 0

    # Loop through the vector to find cycles to rotate.
    for cycleStart, item in enumerate(vector):

        # Find where to put the item.
        pos = cycleStart
        for item2 in vector[cycleStart + 1:]:
            if item2 < item:
                pos += 1

        # If the item is already there, this is not a cycle.
        if pos == cycleStart:
            continue

        # Otherwise, put the item there or right after any duplicates.
        while item == vector[pos]:
            pos += 1
        vector[pos], item = item, vector[pos]
        writes += 1

        # Rotate the rest of the cycle.
        while pos != cycleStart:

            # Find where to put the item.
            pos = cycleStart
            for item2 in vector[cycleStart + 1:]:
                if item2 < item:
                    pos += 1

            # Put the item there or right after any duplicates.
            while item == vector[pos]:
                pos += 1
            vector[pos], item = item, vector[pos]
            writes += 1

    return writes


x = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
w = cycleSort(x) 
print w, x