洗牌算法

假设有数组A[n]，现要打乱元素的顺序，使各个元素等概率地出现在各个位置，称为洗牌操作。

下面是一种简单高效的做法，其思路在从左往右扫描，每次从右侧元素中随机选择一个与当前元素交换位置：

function Shuffle(A, n)
    for i = 0 to n-1
        j = i + rand() % (n - i)
        swap(A[i], A[j])

由于只扫了一遍，时间复杂度为O(n)。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 洗牌算法
    读完本文，你可以去力扣拿下如下题目： 384.打乱数组[https://leetcode-cn.com/probl...
    labuladong阅读 10,982评论 1赞 8
  • C#Shuffle算法(洗牌算法、抽样算法)
    Fisher-Yates Shuffle算法 1.创建一个新的list2.随机取出当前0-list.Count其中...
    罗卡恩阅读 11,130评论 0赞 4
  • 完美洗牌算法
    完美洗牌算法 题目描述： 有个长度为2n的数组 {a1, a2, a3, ..., an, b1, b2, b3,...
    MinoyJet阅读 9,417评论 0赞 2
  • 洗牌算法具体指的是什么
    今天给大家分享一下：洗牌算法具体指的是什么。 一、背景介绍 洗牌算法是我们常见的随机问题，在玩游戏、随机排序时经常...
    slashnie阅读 8,592评论 0赞 0
  • 洗牌算法具体指的是什么
    1.背景介绍 洗牌算法是我们常见的随机问题，在玩游戏、随机排序时经常会碰到，本质是让一个数组内的元素随机排列。 类...
    苟况劝学阅读 5,016评论 0赞 0