Algorithm——配列シャッフルアルゴリズム(7)

Algorithm——配列乱れアルゴリズム
Fisher–Yates shuffleアルゴリズムは非常に効率的で公平なランダム並べ替えアルゴリズム(秩序を乱すアルゴリズム)であり、その時間の複雑さはO(n)である.疑似コードの実現は大体次の通りです.

n = A.length;
for i = 1 to n
    swap A[i] with A[RANDOM(i, n)]

は、第iの反復を行う場合、要素A[i]は、要素A[i]からA[n]までランダムに選択される.i回目の反復後、A[i]は変化しない.
Fisher–Yates shuffleアルゴリズムのJava実装すなわちテストコードは以下の通りです.

public class RandomAlgor {

	static int[] A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

	public static void main(String[] args) {
		fisherYatesShuffle(A);
		System.out.println("      ");
		arrayPrint(A);
	}

	/**
	 *       ：    (Fisher–Yates shuffle    -      )
	 * 
	 * @param A
	 */
	public static void fisherYatesShuffle(int[] A) {

		int rand = 0;
		int swap = 0;
		int n = A.length;

		Random util = new Random();

		for (int i = n - 1; i > 0; i--) {
			rand = Math.abs(util.nextInt() % (i + 1));//               ,     [0,i]
			if (rand != i) {
				swap = A[i];
				A[i] = A[rand];
				A[rand] = swap;
			}
		}
	}

	public static void arrayPrint(int[] array) {
		System.out.print("[");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ", ");
		}
		System.out.println("]");
	}
}