浅析Knuth高效洗牌算法
今天在做一个游戏需求的时候碰到一个问题，问题很简单，给定75个球，编号1-75，需要保证初始化的时候位置是随机的。
显然，我们可以初始化一个数组a，把75个数放进去，然后做一个shuffle函数随机交换其中的元素，这样就是随机的。
我准备这样做一个shuffle，但同时也想看看golang里面是否有这样的接口直接得到结果，看了下还真有，这个函数是rand.perm（n），这个函数会返回一个数组，比如我传入75，会返回一个0-74的随机数组。
arr ：= rand.perm（75）
好奇心驱使我一探究竟，golang会用什么样的方式实现perm函数呢？
打开golang的源代码，在rand.go文件中找到这个函数：
实现很简单，然而初一看有点懵，因为没有用到shuffle，而是一次遍历就把事情给解决了，到底是怎么回事？
仔细分析发现，这个算法非常精巧，每次遍历都是将当前的数i和已经在数组中的随机一个数m［j］进行交换，最终达到了公平随机整个数组的作用。虽然只有短短3行代码，却让人有种震撼的感觉。
顿时觉得golang很nb，确实很高效。
上面这段代码写了4行的注释，大概意思是说不能省去0那一次，看起来没啥用处，但是为了照顾r随机器中的随机序列，还是要加上，不然可能会造成负作用，这里面和随机种子以及此后随机的序列有关，为了对随机序列不产生影响保证公平性，不能省略0。
网上搜索了一下高效洗牌算法，又发现python里面也有这样的函数，这样写的：
for（int i = n - 1; i 》= 0 ; i -- ）
swap（arr［i］， arr［rand（0， i）］） // rand（0， i） 生成 ［0， i］ 之间的随机整数
而这个算法的出处竟然来自于taocp！算法就是大名鼎鼎的 knuth-shuffle，即 knuth 洗牌算法。
看似简单的问题，竟然又扯出knuth，大意了。
能把一件小事情做到极致的人，可以称之为艺术家。knuth名副其实。
最后以knuth的一句话共勉：
a programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
donald e. knuth 1978
聚焦“中国芯”！与产业同行 芯华章受邀出席琴珠澳集成电路产业促进峰会
【直播问答精选（下）】虹科《工艺设备验证》主题研讨会——验证从未如此简单！
从富士康看美帝制造业回流
如何使用STM32G031开发板实现双通道示波器
毫米级Delta机器人研制成功，能够完成制造和医药领域的一系列微操作任务
浅析Knuth高效洗牌算法
Atmosic Technologies与Energous实现业界首例互操作性能量收集，推动无线充电应用发展
如何利用Kinect控制51单片机
欧司朗推出RBG-LEDOsireE4633i
水力发电是如何产生的？
全球半导体市场下滑超两位数几无悬念 芯片厂商凭啥给出增长预期？
迅为STM32MP157开发板入门教程之外设功能验证
为什么单片机的晶振旁边要加电容呢？
火爆的区块链到底可以做一些什么
铁锂电池再受市场关注，安全性是最大优势
Redmi K30 5G网络实测 下载速度达949Mbps
过孔导电滑环安装方法
一种以三个芯片级联而成的窄脉冲小信号运算放大电路
车用显示竞技场：OLED、Mini/Micro 百花齐放
巴特沃斯滤波器优缺点分析
显然，我们可以初始化一个数组a，把75个数放进去，然后做一个shuffle函数随机交换其中的元素，这样就是随机的。
我准备这样做一个shuffle，但同时也想看看golang里面是否有这样的接口直接得到结果，看了下还真有，这个函数是rand.perm（n），这个函数会返回一个数组，比如我传入75，会返回一个0-74的随机数组。
arr ：= rand.perm（75）
好奇心驱使我一探究竟，golang会用什么样的方式实现perm函数呢？
打开golang的源代码，在rand.go文件中找到这个函数：
实现很简单，然而初一看有点懵，因为没有用到shuffle，而是一次遍历就把事情给解决了，到底是怎么回事？
仔细分析发现，这个算法非常精巧，每次遍历都是将当前的数i和已经在数组中的随机一个数m［j］进行交换，最终达到了公平随机整个数组的作用。虽然只有短短3行代码，却让人有种震撼的感觉。
顿时觉得golang很nb，确实很高效。
上面这段代码写了4行的注释，大概意思是说不能省去0那一次，看起来没啥用处，但是为了照顾r随机器中的随机序列，还是要加上，不然可能会造成负作用，这里面和随机种子以及此后随机的序列有关，为了对随机序列不产生影响保证公平性，不能省略0。
网上搜索了一下高效洗牌算法，又发现python里面也有这样的函数，这样写的：
for（int i = n - 1; i 》= 0 ; i -- ）
swap（arr［i］， arr［rand（0， i）］） // rand（0， i） 生成 ［0， i］ 之间的随机整数
而这个算法的出处竟然来自于taocp！算法就是大名鼎鼎的 knuth-shuffle，即 knuth 洗牌算法。
看似简单的问题，竟然又扯出knuth，大意了。
能把一件小事情做到极致的人，可以称之为艺术家。knuth名副其实。
最后以knuth的一句话共勉：
a programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
donald e. knuth 1978
聚焦“中国芯”！与产业同行 芯华章受邀出席琴珠澳集成电路产业促进峰会
【直播问答精选（下）】虹科《工艺设备验证》主题研讨会——验证从未如此简单！
从富士康看美帝制造业回流
如何使用STM32G031开发板实现双通道示波器
毫米级Delta机器人研制成功，能够完成制造和医药领域的一系列微操作任务
浅析Knuth高效洗牌算法
Atmosic Technologies与Energous实现业界首例互操作性能量收集，推动无线充电应用发展
如何利用Kinect控制51单片机
欧司朗推出RBG-LEDOsireE4633i
水力发电是如何产生的？
全球半导体市场下滑超两位数几无悬念 芯片厂商凭啥给出增长预期？
迅为STM32MP157开发板入门教程之外设功能验证
为什么单片机的晶振旁边要加电容呢？
火爆的区块链到底可以做一些什么
铁锂电池再受市场关注，安全性是最大优势
Redmi K30 5G网络实测 下载速度达949Mbps
过孔导电滑环安装方法
一种以三个芯片级联而成的窄脉冲小信号运算放大电路
车用显示竞技场：OLED、Mini/Micro 百花齐放
巴特沃斯滤波器优缺点分析