Java 数组的随机洗牌
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1519736/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Random shuffling of an array
提问by Hubert
I need to randomly shuffle the following Array:
我需要随机洗牌以下数组：
int[] solutionArray = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1};
Is there any function to do that?
有什么功能可以做到这一点吗？
采纳答案by PhiLho
Using Collections to shuffle an array of primitive types is a bit of an overkill...
使用 Collections 对原始类型数组进行混洗有点过头了......
It is simple enough to implement the function yourself, using for example the Fisher–Yates shuffle:
自己实现该功能很简单，例如使用Fisher–Yates shuffle：
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
class Test
{
public static void main(String args[])
{
int[] solutionArray = { 1, 2, 3, 4, 5, 6, 16, 15, 14, 13, 12, 11 };
shuffleArray(solutionArray);
for (int i = 0; i < solutionArray.length; i++)
{
System.out.print(solutionArray[i] + " ");
}
System.out.println();
}
// Implementing Fisher–Yates shuffle
static void shuffleArray(int[] ar)
{
// If running on Java 6 or older, use `new Random()` on RHS here
Random rnd = ThreadLocalRandom.current();
for (int i = ar.length - 1; i > 0; i--)
{
int index = rnd.nextInt(i + 1);
// Simple swap
int a = ar[index];
ar[index] = ar[i];
ar[i] = a;
}
}
}
回答by Dave
Look at the Collectionsclass, specifically shuffle(...).
看Collections班级，具体shuffle(...)。
回答by methodin
Here is a simple way using an ArrayList:
这是使用 的简单方法ArrayList：
List<Integer> solution = new ArrayList<>();
for (int i = 1; i <= 6; i++) {
solution.add(i);
}
Collections.shuffle(solution);
回答by Dan Bray
Here is a working and efficient Fisher–Yates shuffle array function:
这是一个有效且高效的 Fisher–Yates shuffle 数组函数：
private static void shuffleArray(int[] array)
{
int index;
Random random = new Random();
for (int i = array.length - 1; i > 0; i--)
{
index = random.nextInt(i + 1);
if (index != i)
{
array[index] ^= array[i];
array[i] ^= array[index];
array[index] ^= array[i];
}
}
}
or
或者
private static void shuffleArray(int[] array)
{
int index, temp;
Random random = new Random();
for (int i = array.length - 1; i > 0; i--)
{
index = random.nextInt(i + 1);
temp = array[index];
array[index] = array[i];
array[i] = temp;
}
}
回答by KitKat
Collectionsclass has an efficient method for shuffling, that can be copied, so as not to depend on it:
Collections类有一个有效的 shuffle 方法，可以复制，以免依赖它：
/**
* Usage:
* int[] array = {1, 2, 3};
* Util.shuffle(array);
*/
public class Util {
private static Random random;
/**
* Code from method java.util.Collections.shuffle();
*/
public static void shuffle(int[] array) {
if (random == null) random = new Random();
int count = array.length;
for (int i = count; i > 1; i--) {
swap(array, i - 1, random.nextInt(i));
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
回答by SalmaanKhan
Using ArrayList<Integer>can help you solving the problem of shuffling without applying much of logic and consuming less time. Here is what I suggest:
使用ArrayList<Integer>可以帮助您解决洗牌问题，而无需应用太多逻辑并花费更少的时间。这是我的建议：
ArrayList<Integer> x = new ArrayList<Integer>();
for(int i=1; i<=add.length(); i++)
{
x.add(i);
}
Collections.shuffle(x);
回答by Duncan Jones
Here is a complete solution using the Collections.shuffleapproach:
这是使用该Collections.shuffle方法的完整解决方案：
public static void shuffleArray(int[] array) {
List<Integer> list = new ArrayList<>();
for (int i : array) {
list.add(i);
}
Collections.shuffle(list);
for (int i = 0; i < list.size(); i++) {
array[i] = list.get(i);
}
}
Note that it suffers due to Java's inability to smoothly translate between int[]and Integer[](and thus int[]and List<Integer>).
请注意，由于 Java 无法在int[]and Integer[]（以及因此int[]和List<Integer>）之间顺利转换，它会受到影响。
回答by user1050755
Here is a Generics version for arrays:
这是数组的泛型版本：
import java.util.Random;
public class Shuffle<T> {
private final Random rnd;
public Shuffle() {
rnd = new Random();
}
/**
* Fisher–Yates shuffle.
*/
public void shuffle(T[] ar) {
for (int i = ar.length - 1; i > 0; i--) {
int index = rnd.nextInt(i + 1);
T a = ar[index];
ar[index] = ar[i];
ar[i] = a;
}
}
}
Considering that ArrayList is basically just an array, it may be advisable to work with an ArrayList instead of the explicit array and use Collections.shuffle(). Performance tests however, do not show any significant difference between the above and Collections.sort():
考虑到 ArrayList 基本上只是一个数组，建议使用 ArrayList 而不是显式数组并使用 Collections.shuffle()。然而，性能测试没有显示上述和 Collections.sort() 之间的任何显着差异：
Shuffe<Integer>.shuffle(...) performance: 576084 shuffles per second
Collections.shuffle(ArrayList<Integer>) performance: 629400 shuffles per second
MathArrays.shuffle(int[]) performance: 53062 shuffles per second
The Apache Commons implementation MathArrays.shuffle is limited to int[] and the performance penalty is likely due to the random number generator being used.
Apache Commons 实现 MathArrays.shuffle 仅限于 int[] 并且性能损失可能是由于使用了随机数生成器。
回答by Cristiane Dos Santos Costa
Random rnd = new Random();
for (int i = ar.length - 1; i > 0; i--)
{
int index = rnd.nextInt(i + 1);
// Simple swap
int a = ar[index];
ar[index] = ar[i];
ar[i] = a;
}
By the way, I've noticed that this code returns a ar.length - 1number of elements, so if your array has 5 elements, the new shuffled array will have 4 elements. This happens because the for loop says i>0. If you change to i>=0, you get all elements shuffled.
顺便说一下，我注意到这段代码返回了ar.length - 1许多元素，所以如果你的数组有 5 个元素，那么新的无序数组将有 4 个元素。发生这种情况是因为 for 循环说i>0. 如果更改为i>=0，则会将所有元素打乱。
回答by Mr. Polywhirl
You have a couple options here. A list is a bit different than an array when it comes to shuffling.
你有几个选择。在洗牌方面，列表与数组略有不同。
As you can see below, an array is faster than a list, and a primitive array is faster than an object array.
如下所示，数组比列表快，原始数组比对象数组快。
Sample Durations
采样持续时间
List<Integer> Shuffle: 43133ns
Integer[] Shuffle: 31884ns
int[] Shuffle: 25377ns
Below, are three different implementations of a shuffle. You should only use Collections.shuffle if you are dealing with a collection. There is no need to wrap your array into a collection just to sort it. The methods below are very simple to implement.
下面是 shuffle 的三种不同实现。如果你正在处理一个集合，你应该只使用 Collections.shuffle。没有必要将您的数组包装到一个集合中只是为了对其进行排序。下面的方法很容易实现。
ShuffleUtil Class
ShuffleUtil 类
import java.lang.reflect.Array;
import java.util.*;
public class ShuffleUtil<T> {
private static final int[] EMPTY_INT_ARRAY = new int[0];
private static final int SHUFFLE_THRESHOLD = 5;
private static Random rand;
Main Method
主要方法
public static void main(String[] args) {
List<Integer> list = null;
Integer[] arr = null;
int[] iarr = null;
long start = 0;
int cycles = 1000;
int n = 1000;
// Shuffle List<Integer>
start = System.nanoTime();
list = range(n);
for (int i = 0; i < cycles; i++) {
ShuffleUtil.shuffle(list);
}
System.out.printf("%22s: %dns%n", "List<Integer> Shuffle", (System.nanoTime() - start) / cycles);
// Shuffle Integer[]
start = System.nanoTime();
arr = toArray(list);
for (int i = 0; i < cycles; i++) {
ShuffleUtil.shuffle(arr);
}
System.out.printf("%22s: %dns%n", "Integer[] Shuffle", (System.nanoTime() - start) / cycles);
// Shuffle int[]
start = System.nanoTime();
iarr = toPrimitive(arr);
for (int i = 0; i < cycles; i++) {
ShuffleUtil.shuffle(iarr);
}
System.out.printf("%22s: %dns%n", "int[] Shuffle", (System.nanoTime() - start) / cycles);
}
Shuffling a Generic List
打乱通用列表
// ================================================================
// Shuffle List<T> (java.lang.Collections)
// ================================================================
@SuppressWarnings("unchecked")
public static <T> void shuffle(List<T> list) {
if (rand == null) {
rand = new Random();
}
int size = list.size();
if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
for (int i = size; i > 1; i--) {
swap(list, i - 1, rand.nextInt(i));
}
} else {
Object arr[] = list.toArray();
for (int i = size; i > 1; i--) {
swap(arr, i - 1, rand.nextInt(i));
}
ListIterator<T> it = list.listIterator();
int i = 0;
while (it.hasNext()) {
it.next();
it.set((T) arr[i++]);
}
}
}
public static <T> void swap(List<T> list, int i, int j) {
final List<T> l = list;
l.set(i, l.set(j, l.get(i)));
}
public static <T> List<T> shuffled(List<T> list) {
List<T> copy = copyList(list);
shuffle(copy);
return copy;
}
Shuffling a Generic Array
改组通用数组
// ================================================================
// Shuffle T[]
// ================================================================
public static <T> void shuffle(T[] arr) {
if (rand == null) {
rand = new Random();
}
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, i, rand.nextInt(i + 1));
}
}
public static <T> void swap(T[] arr, int i, int j) {
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static <T> T[] shuffled(T[] arr) {
T[] copy = Arrays.copyOf(arr, arr.length);
shuffle(copy);
return copy;
}
Shuffling a Primitive Array
混洗原始数组
// ================================================================
// Shuffle int[]
// ================================================================
public static <T> void shuffle(int[] arr) {
if (rand == null) {
rand = new Random();
}
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, i, rand.nextInt(i + 1));
}
}
public static <T> void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static int[] shuffled(int[] arr) {
int[] copy = Arrays.copyOf(arr, arr.length);
shuffle(copy);
return copy;
}
Utility Methods
实用方法
Simple utility methods to copy and convert arrays to lists and vice-versa.
将数组复制和转换为列表的简单实用方法，反之亦然。
// ================================================================
// Utility methods
// ================================================================
protected static <T> List<T> copyList(List<T> list) {
List<T> copy = new ArrayList<T>(list.size());
for (T item : list) {
copy.add(item);
}
return copy;
}
protected static int[] toPrimitive(Integer[] array) {
if (array == null) {
return null;
} else if (array.length == 0) {
return EMPTY_INT_ARRAY;
}
final int[] result = new int[array.length];
for (int i = 0; i < array.length; i++) {
result[i] = array[i].intValue();
}
return result;
}
protected static Integer[] toArray(List<Integer> list) {
return toArray(list, Integer.class);
}
protected static <T> T[] toArray(List<T> list, Class<T> clazz) {
@SuppressWarnings("unchecked")
final T[] arr = list.toArray((T[]) Array.newInstance(clazz, list.size()));
return arr;
}
Range Class
范围类
Generates a range of values, similar to Python's rangefunction.
生成一系列值，类似于 Python 的range函数。
// ================================================================
// Range class for generating a range of values.
// ================================================================
protected static List<Integer> range(int n) {
return toList(new Range(n), new ArrayList<Integer>());
}
protected static <T> List<T> toList(Iterable<T> iterable) {
return toList(iterable, new ArrayList<T>());
}
protected static <T> List<T> toList(Iterable<T> iterable, List<T> destination) {
addAll(destination, iterable.iterator());
return destination;
}
protected static <T> void addAll(Collection<T> collection, Iterator<T> iterator) {
while (iterator.hasNext()) {
collection.add(iterator.next());
}
}
private static class Range implements Iterable<Integer> {
private int start;
private int stop;
private int step;
private Range(int n) {
this(0, n, 1);
}
private Range(int start, int stop) {
this(start, stop, 1);
}
private Range(int start, int stop, int step) {
this.start = start;
this.stop = stop;
this.step = step;
}
@Override
public Iterator<Integer> iterator() {
final int min = start;
final int max = stop / step;
return new Iterator<Integer>() {
private int current = min;
@Override
public boolean hasNext() {
return current < max;
}
@Override
public Integer next() {
if (hasNext()) {
return current++ * step;
} else {
throw new NoSuchElementException("Range reached the end");
}
}
@Override
public void remove() {
throw new UnsupportedOperationException("Can't remove values from a Range");
}
};
}
}
}
