分享一下心得体会，发牌算法

Question

最近面试遇到过这个问题，看到CSDN上也很多这个问题，我就总结一下吧。目标就是将1-N个自然数乱序，PS，如果对大O表示法不理解可以百度一下废话不多说，直接上代码package com;import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Set;public class Ra { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
Object[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
shuffleBySet(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
} /**
 * 随机交换位子，时间复杂度O(N),空间复杂度O(1),良好
 * java.util.Collections.shuffle方法源代码就是这个算法
 * @param a
 */
public static void shuffleSwap(Object[] a) {
for (int i = 0; i < a.length; i++) {
swap(a, i, (int) (java.lang.Math.random() * a.length));
}
} private static void swap(Object[] a, int m, int n) {
Object t = a[m];
a[m] = a[n];
a[n] = t;
} /**
 * 删除元素法，时间复杂度O(N),空间复杂度O(N)
 * 
 * @param a
 */
public static void shuffleByRemove(Object[] a) {
int r = 0;
List<Object> list = new ArrayList<Object>();
for (int i = 0; i < a.length; i++) {
list.add(a[i]);
}
while (list.size() > 0) {
r = (int) (java.lang.Math.random() * list.size());
a[list.size() - 1] = list.get(r);
list.remove(r);
} } /**
 * 利用Set的不重复性,最佳状态时间复杂度O(N),最糟情况死循环(a.length上千万),空间复杂度O(N)
 * 
 * @param a
 */
public static void shuffleBySet(Object[] a) {
Set<Integer> set = new HashSet<Integer>();
Random R=new Random();
while (set.size() < a.length) {
          set.add(R.nextInt(a.length)+100);
}
Object[] b=a.clone();
int index = 0;
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
Integer i = it.next();
a[index++] = b[i-100];
}
}}