一个公平的洗牌算法 | Knuth-Shuffle

洗牌(随机)算法有很多应用，例如我们平时用的音乐播放器随机播放，棋牌游戏中的洗牌，扫雷游戏中雷的位置随机等等，都会用到洗牌算法。

今天来介绍一个简单，公平，时间复杂度为O(n)的洗牌算法。什么是洗牌算法呢？其实就是将一些数据以公平随机的方式打乱顺序。这个算法，是由Knuth(高纳德)，也就是计算机程序设计艺术的作者发明的。下面我们直接进入正题。

假设有这样一个数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，我们使用Knuth-Shuffle算法将数据打乱。基本流程是这样的，从最后一个数开始，往前遍历，每一次，从当前数和第1个数之间，随机选择一个数，与当前数字进行交换（这里的随机选择就直接使用程序语言中的Random随机一个索引即可）。

例如上面的数组，第一次循环，当前数字为10，我们从1~10之间，随机选择一个数，与10交换，这样第9个索引位就算洗完了，接下来就是第8个索引位，也就是数字为9，我们从第1个索引位与第8个索引位之间，选择一个数，第9交换，这样第8个索引位也就洗完了…。这个算法之所以公平，是因为保证了每一个元素出现在每一个位置上的概率，都是一样的。

代码实现

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        List<int> songList = new List<int>();
        songList.Add(1);
        songList.Add(2);
        songList.Add(3);
        songList.Add(4);
        songList.Add(5);
        songList.Add(6);
        songList.Add(7);
        songList.Add(8);
        songList.Add(9);
        songList.Add(10);

        Random rand = new Random();

        // 开始洗牌算法
        int last = songList.Count - 1;
        for (int i = last; i >= 0; --i)
        {
            // 从当0~当前索引位之间，选择一个数
            int selection = rand.Next(i + 1);
            
            // 索引位对应的数据交换
            int temp = songList[i];
            songList[i] = songList[selection];
            songList[selection] = temp;
        }

        // 打印洗牌后的List
        for (int i = 0; i < songList.Count; ++i)
        {
            Console.Write(songList[i] + " ");
        }

    }
}