一个公平的洗牌算法 | 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] + " ");
}

}
}

更多不错的文章:

https://www.itcodemonkey.com/article/15641.html

Author: Moeif Studio

Permalink: http://blog.moeif.com/2019/12/30/algo-knuth-shuffle/

任何技术问题,可加微信交流,微信: ifloop

搜索并关注微信公众号 [ 萌一小栈 ] 可及时订阅最新技术文章

Comments