Cycle Sort (交换次数最少的排序)

2023-05-13,,

该算法的效率并不高。但是却提供了一个很好的思路。如何让一个序列在最小交换次数下实现有序。

Cycle Sort 翻译成中文是 圈排序

这个圈在于需要交换的数据形成圈。

具体一点:

如:

Array  4 3 2 5 5 6  要处理的数组

Result 2 3 4 5 5 6  结果

pos     0 1 2 3 4 5  下标

从下标0的元素开始观察。4 需要到下标 2 而下标2的元素为 2 需要到下标0 。刚好可以回到4。 也就是形成了 4-2 这样的圈

接下来是3 需要到下标1 而3本身就在1上。那么3自成一圈

再接下来是2。这个2在圈1中所以跳过。

然后是5 5需要在3上(也许你认为4也是可以的。但是实际上我们是按照类似计数排序的手法。算法是稳定的) 5自成一圈

下一个5 也是一样的。

而下一个6同样如此。

实际操作中:

  我们从4开始进行一次类似计数排序一样的位置。多加一步。判断当前位置上的元素是否应该放在4这个位置上。如果不是。就对这个元素所该放的元素继续访问是否应该放在4这个位置上。直到可以。

  然后一直循环下去。

具体还是看 这个博客 的总结好了。详细明白得多。

Cycle Sort (交换次数最少的排序)的相关教程结束。

《Cycle Sort (交换次数最少的排序).doc》

下载本文的Word格式文档,以方便收藏与打印。