50分求,随机排序怎么做？我觉得很难的一个问题，很怪的要求

Question

怎么像我参加ACM的题目，考虑下给你答案。

Answer 1

给我出的原来问题是这样：------------------------
你把问题提高那么多干嘛。
原题目很简单，标记每个班的同学，然后进行随机插入。判断插入位置的前后是否为同样的标记，不同则插入。最后检查是否有前后标记有一样的，否则把相同的AAB或者AAA提取中的中间位置记录，然后寻找非A**的位置进行交换即可。

Answer 2

package test;import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;public class RSortor {
private int n = 1000; private int aN = 100; public RSortor() {
} public RSortor(int n, int an) {
this.n = n;
this.aN = an;
} public void sort() {
List l = new ArrayList();
int sValue = 1;
int value = sValue;
for (int i = 1; i <= n; i++) {
// System.out.println(value);
l.add(new Integer(value));
value += (aN + 1);
value = (value % n) + 1;
if (value == sValue) {
value += 1;
sValue = value;
}
}
// check(l);
l.clear();
l = null;
} private void check(List l) {
if (l == null || l.size() == 0)
return;
Debug.dbg(l.size() + " nums, " + l + " -- ", false);
for (int i = 1; i <= n; i++) {
Integer anI = new Integer(i);
l.remove(anI);
}
if (l.size() == 0)
Debug.dbg(n + "," + aN + " Result is  ok:" + l);
else
Debug.dbg(n + "," + aN + " Result is nok:" + l);
} public static void main(String[] args) {
RSortor rs = new RSortor();
// for (int i = 10; i <= 200; i++) {
// for (int j = 1; j < i; j++) {
// rs.n = i;
// rs.aN = j;
// rs.sort();
// }
// }
rs.aN = 200;
rs.n = 10000;
rs.sort();
}
}class Debug {
private static PrintStream ps; static {
try {
ps = new PrintStream(new FileOutputStream("d:/testAl.log"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
} public static void dbg(Object o, boolean newLine) {
if (newLine)
ps.println(String.valueOf(o));
else
ps.print(String.valueOf(o));
} public static void dbg(Object o) {
ps.println(String.valueOf(o));
}
}

Answer 3

稍微变一下，把sort里的循环中的前两行改下:
[code]
// System.out.println(value);
l.add(new Integer(value));
[/code]
为：
[code]
// System.out.println(yourIntArray[value]);
l.add(new Integer(yourIntArray[value]));
[/code]

Answer 4

有没有更好的办法啊。。To
 momocow 
有点复杂呀。

Answer 5

s of 10 classes: A to JABCDE FGHIJ-ABCDE FGHIJ- ABCDE FGHIJ- ABCDE FGHIJ ....(^_^)

Answer 6

那个分班的算法，你写出来的没有？我看了，算法复杂度，也是o(n).
但是你分班后，用两个循环，而且现在的条件是刚好1000个，每班100个，10个班，如果不是整除的数，你要加例外了。我的也是o(n)，但是就一个循环。而且可以包括不同的数字配合，比如999个，每个都不能是后面23个的情况（这个例子可以任意，包括1000和1）。

Answer 7

呵呵，谢谢楼上啊
最后我是这样实现的，
算法和 
 sunxw18()  提出来的差不多，大致算法是这样
根据需要把数据分组，并设一个三维标志数组，一个记录原始数据所在的组，一个记录数据是否选取过，一个记录它的上一个数据，根据上一个数据所在的组，随机选取不在同一个组并且标志未选取的数据作为下个数据，第一个数据单独处理,它没有前一个数据

Answer 8

dreadroad:基本同意的你的算法，不过我想你需要考虑取下一组时为相邻分组的特殊情况，当然你也可以根据当前分组的好，间隔一个分组，这样就好点。
不过启用一个三维数组似乎过多的占用空间了，中间判断语句会比较复杂的吧。其实我的算法的思想基础也是分组：我是按照10（比如是an）这个数字，取11（an+1），然后取模结果会变成12（an+2），保证数是当前的10(an)之后的数；实际上相当于第一次取第一分组的第一个，然后都取每个分组中第3个。这里还有一个特殊情况，下一次再回到第一组时，如果和上一次的第一组数相同，就取第一组的下一个数，这样保证不会重复；而且第二次如果不出现上述特例情况，以后的每一次组循环都不会再出现。