Cycle Sort (交换次数最少的排序)
浏览数：28 /
时间：2015年06月08日
该算法的效率并不高。但是却提供了一个很好的思路。如何让一个序列在最小交换次数下实现有序。
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这个位置上。直到可以。
然后一直循环下去。
具体还是看 这个博客 的总结好了。详细明白得多。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
