洗牌算法

发表于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 2 分钟

第一次接触洗牌算法是在一次面试上，面试官要求我写出一个算法将一个1～100的有序数组打乱，不考虑性能，那次我想了许久，想到一种基于二叉排序的方式实现了随机洗牌，但是那个性能呢，惨不忍睹。后来详细学习排序算法的时候，发现为了保证快速排序的性能，需要在排序之前对排序的数组进行洗牌操作。

为什么不基于一般排序算法做洗牌？

众所周知，一般排序算法在在性能上以快速排序最好吧，时间复杂度基本在N*logN，空间复杂度在logN，当然三切分快速排序更好一些。所有算法中空间复杂度最好时为1，这当然是最好的。详细见对于基础排序算法的简要总结。但是在排序算法中没有能够达到时间复杂度N的线性的。而在洗牌算法中，我们随便便能实现N的线性的时间复杂度，因此基于排序算法做洗牌不可取。

洗牌算法第一版

初次想的是一个排列好的数组，再新建一个长度相等的数组，每次通过随机数，随机一个N以内的数作为下标将其添加到新数组，并将该随机下标与N为下标的数交换，当然N需要自减。在N开始的时候为数组长度减1的值（保证下标最大而不越界）。那么最后会形成一个任意数组在数组内的某一位置的概率都是1/N的随机数组。

1
2
3
4
5
6
7
8
9
10
public static Comparable[] Shuffle1(Comparable[] c) {
    Comparable[] a = new Comparable[c.length];
    int N = c.length - 1;
    for (int i = 0; i < c.length; i++, N--) {
        int ran = intRandom(0, N);
        a[i] = c[ran];
        c[ran] = c[N];
    }
    return a;
}

这种算法相比较之前打算基于一般排序算法求解的方式，在时间复杂度上有了很大的提升。在时间复杂度上，这种算法保证了N次循环（N为数组长度），N次获取随机值，N次交换（但是有2N次数组元素赋值操作）实现了分部均匀的洗牌算法。但是它的缺点是需要另建数组，使得空间复杂度增加。

在算法中使用了随机数的intRandom函数如下

1
2
3
4
5
6
7
private static int intRandom(int min, int max) {
    if (min > max) 
        throw new IllegalArgumentException("min can not bigger than max");
    if (max == min) 
        return max;
    return new Random().nextInt(max - min + 1) + min;
}

洗牌算法第二版

为了减少空间复杂度，使得算法在原地进行洗牌操作，尝试着将算法改进。在本算法中使用随机生成一个下标，使得对应的数与第一个i个数交换（i会从0到N-1自增）。

1
2
3
4
5
6
7
8
9
public static void Shuffle2(Comparable[] c) {
    int N = c.length;
    for (int i = 0; i < N; i++) {
        Comparable mid = c[0];
        int ran = intRandom(0, N-1);
        c[0] = c[ran];
        c[ran] = mid;
    }
}

当然在本算法中，空间复杂度是1，达到最小。而时间复杂度也没有很大升高，依然需要N次循环，N次随机，N次交换（但是有3N次赋值操作）。因为对于数组中的每个数都会进行同样的操作，不因为数组元素顺序等变化，因此对于任意一个数分布在某个位置的概率是相同的。所有这是目前我发现的最好的洗牌算法。

附

本文仅讲述一些自我对于洗牌算法的一些了解以及自我的一些思考以及实现，在目前我的了解中，这两种洗牌算法是最好的了，如有更好，请指出，共同学习。