昨天看知乎的时候看到了洗牌算法(Knuth shuffle, 最初版本叫Fisher–Yates shuffle/ Sattolo’s algorithm)：世界上有哪些代码量很少，但很牛逼很经典的算法或项目案例？ - 知乎
具体的问题是：如何打乱一个数组，确保数组乱的很随机。
伪代码的实现如下：
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
在整个过程中，这个算法保证了每一个元素出现在每一个位置的概率是相等的。
洗牌算法时间复杂度为O(N)，并且被证明为完美的随机排序。
更具体的说明参考维基：Fisher–Yates shuffle - Wikipedia
然后我就想到了Python的random库中的shuflle函数，shuflle函数的作用就是打乱数组，我觉得具体的实现应该就是这个洗牌算法。
然后去查看random.shuffle的源码：
_inst = Random()
shuffle = _inst.shuffle
def shuffle(self, x, random=None):
"""Shuffle list x in place, and return None.
Optional argument random is a 0-argument function returning a
random float in [0.0, 1.0); if it is the default None, the
standard random.random will be used.
"""
if random is None:
randbelow = self._randbelow
for i in reversed(range(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = randbelow(i+1)
x[i], x[j] = x[j], x[i]
else:
_int = int
for i in reversed(range(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = _int(random() * (i+1))
x[i], x[j] = x[j], x[i]
可以看出使用了洗牌算法。
参考：How Python random shuffle works? - Software Engineering Stack Exchange
文档信息
- 本文作者：last2win
- 本文链接：https://last2win.com/2020/01/16/shuffle/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）