【数据结构笔记46】Sort with Swap(0,*)只允许交换0的排序

本次笔记内容：
习题-SWS.1 环的分类
习题-SWS.2 算法示例

题意理解

如上图，本题目中仅利用与0交换的操作，以达到排序目的。联想到环排序。0其实就是空位。

题目要求输出0的使用次数。

因此，本题目转换为对环进行处理即可。

环的分类

如上图，环分为三类。对于第三种情况，先把0交换到环里，则环里一共有n+1个元素。之前要把0交换到环里，因此需要在(n+1)-1基础上再加1。

若N个元素的序列包含S个单元环、K个多元环，则交换次数为：$n_0 - 1 + \sum^{K-1}_{i=1}(n_i + 1)=\sum^{K-1}_{i=0} n_i + K - 2 = N - S + K - 2$n0​−1+i=1∑K−1​(ni​+1)=i=0∑K−1​ni​+K−2=N−S+K−2

因此本题目中输出，即为上式。

算法示例

如上图，定义一个指针数组，记录每个元素当前的位置。比如0现在放的位置是7，则T[0]=7。

如上图，对环进行移动。并且在遇到0操作时停下，判断本环的结束。并且判断有没有0，来决定加数。第一个环结束，进行3+。

最终，结果为3+6=9！

浙江大学，数据结构，完结撒花！2019年10月23日22:27:53~图书馆正好关门！