中国大学MOOC-数据结构基础习题集、08-3、Sort with Swap(0,*)

题目链接：http://www.patest.cn/contests/mooc-ds/08-3

题目分析：这是一道考察排序算法的一道题。但是排序有要求，每次只能用数字0和其他数字进行排序。因此题目的名字叫做swap(0,*)。博主由于最开始没有思路，看了讨论区的几个帖子，发现大家大概有几种思路：

　　1. azlisme同学在讨论区发出的帖子，据说是可以在线性时间内AC，感觉比较厉害，感兴趣的同学可以看一下：

　　　　http://www.icourse163.org/learn/zju-93001#/learn/forumdetail?pid=582017

　　2. 天堂人间的博客，博主是学习这个做出的代码。相似度比较高。不同的是博主没有把数组的“内容”和“下标”倒过来。所以想看原帖的可以看一下：

　　　　http://blog.csdn.net/tiantangrenjian/article/details/13749067

特别说明：

　　1. 有的同学case1和case2超时（就像博主一样），可能是你在找下标不在对应位置的时间太长。相应部分可以参考一下我的代码【42~52行】：

 1         int j;        // 如果这里不从firstNoZero开始，则case1会超时
 2         for(j=firstNotZero; j<n; j++)
 3         {
 4             if(myNum[j] != j)
 5             {
 6                 firstNotZero = j;
 7                 break;
 8             }
 9         }
10         if(j==n)      // 如果j到达了最后，说明已经排好序了
11             firstNotZero = 0;

　　2. 博主的思路找到第一个不在位置（即下标与数值不等）的firstNotZero【18~26行】。如果数组第0个元素为0，就发生一次交换【29~34行】。如果第0个元素不为0，则一直交换直到第0个元素为0【35~41行】。接下来还要找到下标不在位置【42~52行】。一直循环下去，知道所有元素都在位置。

代码分析：

　　代码很短，该说的都在特别说明2里了。这里没啥好说的了。如果不懂的地方或者有错误的地方，可以在评论区里留言。

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n;
 9     cin >> n;
10     vector<int> myNum;
11     for(int i=0; i<n; i++)
12     {
13         int numTemp;
14         cin >> numTemp;
15         myNum.push_back(numTemp);
16     }
17     int countS = 0;
18     int firstNotZero = 0;
19     for(int j=1; j<n; j++)
20     {
21         if(myNum[j] != j)
22         {
23             firstNotZero = j;
24             break;
25         }
26     }
27     while(firstNotZero != 0)
28     {
29         if(myNum[0] == 0)
30         {
31             myNum[0] = myNum[firstNotZero];
32             myNum[firstNotZero] = 0;
33             countS++;
34         }
35         while(myNum[0] != 0)       // 只要myNum[0]不为0，就一直交换
36         {
37             int t = myNum[0];
38             myNum[0] = myNum[myNum[0]];
39             myNum[t] = t;
40             countS++;
41         }
42         int j;        // 如果这里不从firstNoZero开始，则case1会超时
43         for(j=firstNotZero; j<n; j++)
44         {
45             if(myNum[j] != j)
46             
47                 firstNotZero = j;
48                 break;
49             }
50         }
51         if(j==n)      // 如果j到达了最后，说明已经排好序了
52             firstNotZero = 0;
53     }
54     cout << countS << endl;
55     return 0;
56 }

AC成果：