我需要对以下数组进行随机排序：
int[] solutionArray = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1};
有没有可以做到这一点的函数？
32个回答
295
使用集合来洗牌原始类型的数组有些过度了...
你可以很容易地自己实现此函数，例如使用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;
}
}
}
- PhiLho
16
72最好使用Collections.shuffle(Arrays.asList(array));而不是自己编写洗牌算法。 - Louis Hong
28@Louie
Collections.shuffle(Arrays.asList(array))不能生效，因为Arrays.asList(array)返回的是Collection<int[]>而不是你所想的Collection<Integer>。请注意修改。 - Adam Stelmaszczyk3为什么
Collections.shuffle 是过度设计？ - exhuma19因为如果您有一个包含成千上万或百万个原始值的数组需要排序，那么为了进行排序而将每个值都封装在对象中会导致一些代价，无论是在内存还是CPU方面。 - PhiLho
16这不是 Fisher-Yates 洗牌算法，而是 Durstenfeld 洗牌算法。原始的 Fisher-Yates 算法的时间复杂度为 O(n^2)，非常慢。请参见链接了解 Durstenfeld 洗牌算法的详细信息。 - Pacerier
显示剩余11条评论
189
这里有一种使用 ArrayList 的简单方法：
List<Integer> solution = new ArrayList<>();
for (int i = 1; i <= 6; i++) {
solution.add(i);
}
Collections.shuffle(solution);
- methodin
4
17你可以简单地使用
Collectons.shuffle(Arrays.asList(solutionArray));。该代码会打乱一个包含在solutionArray中的列表，不会改变列表中元素的数量或值。 - FindOutIslamNow1@Timmos，你错了。Arrays.asList 包装的是原始数组，因此修改它会修改原始数组。这就是为什么你不能添加或删除，因为数组大小是固定的。 - Nand
@Nand 我不确定当时我在想什么，但是看源代码，确实 Arrays.asList 方法创建了一个由给定数组支持的 ArrayList。感谢你指出来。我删除了之前的评论（无法编辑）。 - Timmos
3这个答案怎么回事？它甚至没有试图回答标题中的问题。甚至连任何数组都看不到。 - Andrey Tyukin
109
这是一个可工作且高效的Fisher-Yates随机打乱数组函数：
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];
}
}
}
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;
}
}
- Dan Bray
7
1投票支持，因为我需要一个不需要创建整数集合的高开销解决方案。 - mwk
2第二种实现难道没有可能与自己的索引进行交换吗？
random.nextInt(int bound)是排除边界的，但如果将i + 1作为参数传递给它，则index和i有可能相同。 - bmcentee14834在随机排列中，可以将一个元素与其自身交换。不理解这一点削弱了恩格玛密码机的安全性，并帮助艾伦·图灵破译了它。详情请见：https://zh.wikipedia.org/wiki/%E6%81%A9%E6%A0%BC%E9%A9%AC%E7%A0%81_%E5%88%86%E6%9E%90#%E6%81%A9%E6%A0%BC%E9%A9%AC%E7%A0%81%E6%9C%BA - Ellen Spertus
6
Xor 技巧在 CPU 没有置换指令且没有可用寄存器时，非常适合交换 CPU 寄存器。但是对于循环内部交换数组元素，我看不到任何好处。对于临时本地变量，没有理由在循环外声明它们。 - Holger1在循环外声明
temp变量会稍微更有效率一些。使用XOR技巧应该比使用temp变量更快，但要确保的唯一方法是进行基准测试。 - Dan Bray显示剩余2条评论
30
Collections类有一个高效的洗牌方法，可以被复制，以不依赖于它：
/**
* 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;
}
}
- KitKat
3
“为了不依赖于它”？如果可能的话，我更愿意依赖于它。 - shmosel
@shmosel 那就随意使用吧。确保导入了所需的类，并将数组转换为列表，使用
Arrays.asList。还需要将结果列表转换回数组。 - KitKat3你不能在原始数组上使用
Arrays.asList() 方法。但是你不需要将其转换回来，因为它只是一个包装器。 - shmosel14
查看 Collections 类，特别是 shuffle(...) 方法。
- Dave
3
8在Android中如何使用Collections类？需要进行特殊的导入（CRTL SHIFT O无法使用）吗？ - Hubert
@Hubert 它应该是
java.util包的一部分。自v1.2以来，它已成为标准库的一部分。 - MauganRa3为了使您的回答更加自包含，它应该包括示例代码。例如：
import java.util.Collections; shuffle(solutionArray);（翻译您所提供的英文句子） - Stevoisiak12
你有几个选择。在洗牌方面，列表与数组有些不同。
从下面可以看出，数组比列表更快，原始数组比对象数组更快。
从下面可以看出，数组比列表更快，原始数组比对象数组更快。
样本持续时间
List<Integer> Shuffle: 43133ns
Integer[] Shuffle: 31884ns
int[] Shuffle: 25377ns
以下是三种不同的洗牌算法实现。如果您处理的是集合，请使用Collections.shuffle。没有必要将数组包装成集合来进行排序。下面的方法非常简单易实现。
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);
}
对通用列表进行洗牌
// ================================================================
// 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;
}
打乱一个通用数组
// ================================================================
// 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
// ================================================================
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;
}
范围类
生成一系列值，类似于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");
}
};
}
}
}
- Mr. Polywhirl
1
2你没有同时计时相同的事情，而是每个只计时一次（然后它们的顺序很重要，你忘记了运行时优化）。在任何计时之前，你应该调用
range、toArray和toPrimitive，并循环以便能够得出结论（伪代码：多次执行{生成列表、arr和iarr；计时洗牌列表；计时洗牌arr；计时洗牌iarr}）。我的结果是：第1次：list: 36017ns，arr: 28262ns，iarr: 23334ns。第100次：list: 18445ns，arr: 19995ns，iarr: 18657ns。这只是表明int[]已经被代码预先优化了，但它们在运行时优化方面几乎是等效的。 - syme11
这里是使用 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);
}
}
请注意，由于Java无法平滑地在int[]和Integer[]之间进行翻译（因此int[]和List<Integer>），因此它会受到影响。
- Duncan Jones
9
以下代码将对数组进行随机排序。
来源： http://www.programcreek.com/2012/02/java-method-to-shuffle-an-int-array-with-random-order/
// Shuffle the elements in the array
Collections.shuffle(Arrays.asList(array));
来源： http://www.programcreek.com/2012/02/java-method-to-shuffle-an-int-array-with-random-order/
- Rajib Biswas
2
2请注意，它不适用于原始数组，因为Arrays.asList将原始数组视为一个元素。 - barwnikk
如果数组包含许多对象而不是通常的基本类型数组呢？ - gumuruh
9
使用ArrayList<Integer>可以帮助您解决洗牌问题，而不需要应用太多的逻辑并且消耗更少的时间。以下是我的建议：
ArrayList<Integer> x = new ArrayList<Integer>();
for(int i=1; i<=add.length(); i++)
{
x.add(i);
}
Collections.shuffle(x);
- SalmaanKhan
2
可能不是后者——_消耗更少的时间_。事实上，这肯定比上面的原始实现要慢。 - Boris the Spider
1对于那些复制代码的人，请注意 "for循环" 中的 i=1，也许你需要将其改为 i=0。 - Boris Karloff
5
现在您可以使用Java 8：
Collections.addAll(list, arr);
Collections.shuffle(list);
cardsList.toArray(arr);
- Иван Николайчук
1
3这段代码中没有Java8特定的内容。它可以在Java2中使用。不过，在你修复先使用
list后突然引用cardsList之间的不一致性之后，它就能正常工作了。但由于你需要创建被省略的临时list，所以与这里多次展示的Collections.shuffle(Arrays.asList(arr));方法相比并没有任何优势，该方法自Java2以来也可用。 - Holger网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
List<int[]>。请参考我的答案，使用Collections.shuffle()来实现你想要的结果。 - Duncan Jonesshuffle方法。 - k314159