随机排序

「爱情、让人受尽委屈。」 2022-09-18 10:45 101阅读 0赞

最近正在看《算法导论》，里面有不少让我耳目一新的算法，由于看的比较慢，龟速更新

下面是大致叙述随机排序核心算法的伪代码

代码中A代表待随机排序的数组，length\[A\]代表该数组的长度，swap代表把两个变量的值互换

n←length[A]
    for i←1 to n-1
        do swap A[i] ←→ A[RANDOM(i, n)]

解读  
该段伪代码的大致意思为，遍历一个待随机排序的数组，每次循环的时候，都将当前数与其后面的随机一个数进行交换（这就代表，其之前已被遍历过的数组元素不会再被改变）。

下面，随机拿一组数做示例

初始数组\{1,2,3,4,5,6,7,8,9,10\}

开始随机过程

↓

1,2,3,4,5,6,7,8,9,10    随到的下标：2，即将当前数与第2个数进行交换

↓

2,1,3,4,5,6,7,8,9,10    随到的下标：4

↓

2,4,3,1,5,6,7,8,9,10    随到的下标：10

↓

2,4,10,1,5,6,7,8,9,3    随到的下标：5

↓

2,4,10,5,1,6,7,8,9,3    随到的下标：8

↓

2,4,10,5,8,6,7,1,9,3    随到的下标：8

↓

2,4,10,5,8,1,7,6,9,3    随到的下标：9

↓

2,4,10,5,8,1,9,6,7,3    随到的下标：9

↓

2,4,10,5,8,1,9,7,6,3    随到的下标：10

最终数组：2,4,10,5,8,1,9,7,3,6

从上例中可以看出，最终数组已被随机打乱

下面附上一段自己写的随机排序的Java代码，如有不足之处，还请指出

public class Test {
    	public static void main(String[] args) {
    		final int SUM=100;
    		int a=(int) Math.round(Math.random()*100);
    		int[] arr=new int[SUM];
    		for(int i=0;i<SUM;i++)
    			arr[i]=i+1;
    		for(Integer i:arr)
    			System.out.print(i+" ");
    		System.out.println("\n=====================================");
    		for(int i=0;i<SUM-1;i++){  //从这开始才是随机排序
    			int temp=arr[i];
    			int random=(int) Math.round(Math.random()*(SUM-i-1))+i;
    			arr[i]=arr[random];
    			arr[random]=temp;
    		}
    		for(Integer i:arr)
    			System.out.print(i+" ");
    	}
    }