algorithm - 循环排序算法

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