循环排序算法

Question

循环排序算法

algorithmsortingcycle-sort

7

我在浏览互联网时发现有一种叫做循环排序的算法可以使内存写入最小化。但我找不到该算法的任何资料。如何检测数组中是否存在循环？有人能给出这个算法的完整解释吗？

- gogo

可能是优化循环排序实现的重复问题。 - zengr

术语“cycle”表示循环符号：http://en.wikipedia.org/wiki/Cycle_notation - zengr

当我阅读《优化循环排序实现》的帖子时，我感觉它与选择排序相同，即通过多次迭代尝试找到最小位置。循环排序与选择排序有何不同之处？是因为该算法如果数字已经在正确的位置上，则不会交换数字，还是有其他原因？ - gogo

如果您能发布一个演示循环排序的示例，那将非常有帮助。 - gogo

请问有人能告诉我这个的算法吗？ - gogo

@gogo 你确定你没有在这里找到它吗 :) https://en.wikipedia.org/wiki/Cycle_sort - roottraveller

2个回答

0

如果有人需要，这里是一个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

- Aman Verma

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

循环排序算法的灵感来自于一种叫做“循环分解”的东西。循环分解最好通过例子来解释。假设你有这个数组：

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²) 的运行时间——但不需要进行任何写操作。