# 使用 Fisher-Yates 隨機播放算法隨機播放給定數組 > 原文： [https://www.geeksforgeeks.org/shuffle-a-given-array/](https://www.geeksforgeeks.org/shuffle-a-given-array/) 給定一個數組，編寫一個程序以生成數組元素的隨機排列。 還問這個問題為“洗牌”或“給定數組隨機化”。 這里的隨機化意味著數組元素的每個排列都應該具有相同的可能性。  令給定數組為`arr[]`。 一個簡單的解決方案是創建一個輔助數組`temp[]`，該數組最初是`arr[]`的副本。 從`temp[]`中隨機選擇一個元素，將隨機選擇的元素復制到`arr[0]`中，然后從`temp[]`中刪除所選元素。 重復相同的過程 n 次，并將元素復制到`arr[1], arr[2], …`。此解決方案的時間復雜度為`O（n ^ 2）`。 [Fisher-Yates 混洗算法](http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm)在`O(n)`時間復雜度下工作。 這里的假設是，給我們一個函數`rand()`，它在`O(1)`時間內生成隨機數。 的想法是從最后一個元素開始，將其與整個數組（包括最后一個）中隨機選擇的元素交換。 現在考慮從 0 到`n-2`的數組（大小減小 1），并重復該過程直到我們找到第一個元素。 以下是詳細的算法 ``` To shuffle an array a of n elements (indices 0..n-1): for i from n - 1 downto 1 do j = random integer with 0 <= j <= i exchange a[j] and a[i] ``` 以下是該算法的實現。 ## C++ ```cpp // C++ Program to shuffle a given array? #include<bits/stdc++.h>? #include <stdlib.h>? #include <time.h>? using namespace std;? // A utility function to swap to integers? void swap (int *a, int *b)? {? ????int temp = *a;? ????*a = *b;? ????*b = temp;? }? // A utility function to print an array? void printArray (int arr[], int n)? {? ????for (int i = 0; i < n; i++)? ????????cout << arr[i] << " ";? ????cout << "\n";? }? // A function to generate a random? // permutation of arr[]? void randomize (int arr[], int n)? {? ????// Use a different seed value so that? ????// we don't get same result each time ????// we run this program? ????srand (time(NULL));? ????// Start from the last element and swap? ????// one by one. We don't need to run for? ????// the first element that's why i > 0? ????for (int i = n - 1; i > 0; i--)? ????{? ????????// Pick a random index from 0 to i? ????????int j = rand() % (i + 1);? ????????// Swap arr[i] with the element? ????????// at random index? ????????swap(&arr[i], &arr[j]);? ????}? }? // Driver Code int main()? {? ????int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};? ????int n = sizeof(arr) / sizeof(arr[0]);? ????randomize (arr, n);? ????printArray(arr, n);? ????return 0;? }? // This code is contributed by? // rathbhupendra ``` ## C ``` // C Program to shuffle a given array #include <stdio.h> #include <stdlib.h> #include <time.h> // A utility function to swap to integers void swap (int *a, int *b) { ????int temp = *a; ????*a = *b; ????*b = temp; } // A utility function to print an array void printArray (int arr[], int n) { ????for (int i = 0; i < n; i++) ????????printf("%d ", arr[i]); ????printf("\n"); } // A function to generate a random permutation of arr[] void randomize ( int arr[], int n ) { ????// Use a different seed value so that we don't get same ????// result each time we run this program ????srand ( time(NULL) ); ????// Start from the last element and swap one by one. We don't ????// need to run for the first element that's why i > 0 ????for (int i = n-1; i > 0; i--) ????{ ????????// Pick a random index from 0 to i ????????int j = rand() % (i+1); ????????// Swap arr[i] with the element at random index ????????swap(&arr[i], &arr[j]); ????} } // Driver program to test above function. int main() { ????int arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; ????int n = sizeof(arr)/ sizeof(arr[0]); ????randomize (arr, n); ????printArray(arr, n); ????return 0; } ``` ## Java ```java // Java Program to shuffle a given array import java.util.Random; import java.util.Arrays; public class ShuffleRand? { ????// A Function to generate a random permutation of arr[] ????static void randomize( int arr[], int n) ????{ ????????// Creating a object for Random class ????????Random r = new Random(); ????????// Start from the last element and swap one by one. We don't ????????// need to run for the first element that's why i > 0 ????????for (int i = n-1; i > 0; i--) { ????????????// Pick a random index from 0 to i ????????????int j = r.nextInt(i+1); ????????????// Swap arr[i] with the element at random index ????????????int temp = arr[i]; ????????????arr[i] = arr[j]; ????????????arr[j] = temp; ????????} ????????// Prints the random array ????????System.out.println(Arrays.toString(arr)); ????} ????// Driver Program to test above function ????public static void main(String[] args)? ????{ ?????????int[] arr = {1, 2, 3, 4, 5, 6, 7, 8}; ?????????int n = arr.length; ?????????randomize (arr, n); ????} } // This code is contributed by Sumit Ghosh ``` ## Python ``` # Python Program to shuffle a given array import random # A function to generate a random permutation of arr[] def randomize (arr, n): ????# Start from the last element and swap one by one. We don't ????# need to run for the first element that's why i > 0 ????for i in range(n-1,0,-1): ????????# Pick a random index from 0 to i ????????j = random.randint(0,i+1) ????????# Swap arr[i] with the element at random index ????????arr[i],arr[j] = arr[j],arr[i] ????return arr # Driver program to test above function. arr = [1, 2, 3, 4, 5, 6, 7, 8] n = len(arr) print(randomize(arr, n)) # This code is contributed by Pratik Chhajer ``` ## C# ```cs // C# Code for Number of digits? // in the product of two numbers using System; class GFG {? // A Function to generate a // random permutation of arr[] ????static void randomize(int []arr, int n) ????{ ????????// Creating a object ????????// for Random class ????????Random r = new Random(); ????????// Start from the last element and ????????// swap one by one. We don't need to ????????// run for the first element? ????????// that's why i > 0 ????????for (int i = n - 1; i > 0; i--)? ????????{ ????????????// Pick a random index ????????????// from 0 to i ????????????int j = r.Next(0, i+1); ????????????// Swap arr[i] with the ????????????// element at random index ????????????int temp = arr[i]; ????????????arr[i] = arr[j]; ????????????arr[j] = temp; ????????} ????????// Prints the random array ????????for (int i = 0; i < n; i++) ????????Console.Write(arr[i] + " "); ????} // Driver Code static void Main() { ????int[] arr = {1, 2, 3, 4,? ?????????????????5, 6, 7, 8}; ????int n = arr.Length; ????randomize (arr, n); } } // This code is contributed by Sam007 ``` ## PHP ```php <?php // PHP Program to shuffle? // a given array // A function to generate // a random permutation of arr[] function randomize ($arr, $n) { ????// Start from the last element? ????// and swap one by one. We? ????// don't need to run for the ????// first element that's why i > 0 ????for($i = $n - 1; $i >= 0; $i--) ????{ ????????// Pick a random index ????????// from 0 to i ????????$j = rand(0, $i+1); ????????// Swap arr[i] with the? ????????// element at random index ????????$tmp = $arr[$i]; ????????$arr[$i] = $arr[$j]; ????????$arr[$j] = $tmp; ????} ????for($i = 0; $i < $n; $i++) ????echo $arr[$i]." "; } // Driver Code $arr = array(1, 2, 3, 4,? ?????????????5, 6, 7, 8); $n = count($arr); randomize($arr, $n); // This code is contributed by mits ?> ``` **輸出**： ``` 7 8 4 6 3 1 2 5 ``` 上面的函數假定`rand()`生成一個隨機數。 **時間復雜度**：`O(n)`，假設函數`rand()`需要`O(1)`時間。 **這是如何工作的？** 第`i`個元素（包括最后一個元素）到達最后位置的概率為`1 / n`，因為我們在第一次迭代中隨機選擇了一個元素。 通過將`i`元素分為兩種情況，可以證明 ith 元素到達倒數第二個位置的概率為`1 / n`。 *情況 1：`i = n-1`（最后一個元素的索引）*： 最后一個元素到達倒數第二個位置的概率為=（最后一個元素沒有停留在其最后位置的概率 原始位置）x（再次選擇在上一步中選擇的索引以便交換最后一個元素的概率） 因此，概率`= ((n-1) / n) x (1 / (n-1)) = 1 / n` *情況 2：`0 < i < n-1`（非最后索引）*： 第 i 個元素移至第二位置的概率=（概率 第一個元素在上一次迭代中未被選擇）x（在此迭代中選擇第 i 個元素的概率） 因此，概率`=((n-1) / n) x (1 / (n-1))= 1 / n` 我們可以輕松地將上述證明推廣到其他位置。