gog*_*ogo 5 sorting algorithm cycle-sort
当我发现有一种称为循环排序的算法时,我正在浏览互联网,这使得内存写入次数最少.但我无法在任何地方找到算法.如何检测循环是否存在阵列？任何人都能对这个算法做出完整的解释吗？
tem*_*def 16
循环排序算法的动机是称为循环分解.循环分解最好用例子来解释.我们假设你有这个数组:
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和3交换到1是.换句话说,元件1和3向前循环一个位置.
作为上述观察的结果,我们说序列4 3 0 1 2具有循环分解(0 2 4)(1 3).在这里,括号中的每组术语意味着"循环地循环这些元素".这意味着将0循环到2为2的点,2为4的点,4为0的点,然后循环1到3为3的点,3为1的点.
如果您对特定数组进行循环分解,则可以按排序顺序将其取回,从而通过将所有内容向后循环一个点来创建最少的写入次数.循环排序背后的想法是尝试确定输入数组的循环分解是什么,然后反转它以将所有内容放回原位.
这方面的一部分挑战是弄清楚最初所有的东西,因为循环分解假设你知道这一点.通常,循环排序通过转到每个元素并计算有多少元素小于它来工作.这很昂贵 - 它有助于排序算法的Θ(n 2)运行时 - 但不需要任何写入.