1. package lhz.algorithm.chapter.five; 
2.  
3. /** 
4.  * 随机数组两种实现，《算法导论》第五章第三节 
5.  * 本文地址：http://mushiqianmeng.blog.51cto.com/3970029/734384
6.  * @author lihzh(苦逼coder) 
7.  */ 
8. public class RandomArray { 
9.  
10.     private static int[] arrayOne = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
11.             11, 12, 13 }; 
12.     private static int[] arrayTwo = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
13.             11, 12, 13 }; 
14.  
15.     public static void main(String[] args) { 
16.         //随机方式一，排列数组一 
17.         permuteBySorting(arrayOne); 
18.         //打印数组一 
19.         printArray(arrayOne); 
20.         System.out.println(""); 
21.         //随机方式二，排列数组二 
22.         randomizeInPlace(arrayTwo); 
23.         //打印数组二 
24.         printArray(arrayTwo); 
25.     } 
26.  
27.     /** 
28.      * 随机化数组方式一，采用优先级数组比照方式 
29.      * PERMUTE-BY-SORTING(A)  
30.      * 1 n ← length[A]  
31.      * 2 for i ← 1 to n  
32.      * 3 do P[i] =RANDOM(1, n^3)  
33.      * 4 sort A, using P as sort keys  
34.      * 5 return A 
35.      */ 
36.     private static void permuteBySorting(int[] input) { 
37.         int n = input.length; 
38.         int[] p = new int[n]; 
39.         for (int i = 0; i < n; i++) { 
40.             p[i] = randomValue(n); 
41.         } 
42.         mergeSort(input, p); 
43.         /* 
44.          *复杂度分析： 
45.          *因为采用了合并排序，所以可知复杂度为:Θ(n lg n)  
46.          */ 
47.     } 
48.      
49.     /** 
50.      * 随机化数组方式二，直接位置交换方式 
51.      * 复杂度为：O(n) 
52.      * RANDOMIZE-IN-PLACE(A) 
53.      *  1 n ← length[A] 
54.      *  2 for i ← to n 
55.      *  3 do swap A[i] ↔ A[RANDOM(i, n)] 
56.      * @param input 
57.      */ 
58.     private static void randomizeInPlace(int[] input) { 
59.         int n = input.length; 
60.         for (int i = 0; i < n; i++) { 
61.             int index = (int) (Math.random() * (n - i - 1) + i); 
62.             int temp = input[index]; 
63.             input[index] = input[i]; 
64.             input[i] = temp; 
65.         } 
66.     } 
67.      
68.     /** 
69.      * 产生从1到n^3的随机数 
70.      * @param n 
71.      * @return 
72.      */ 
73.     private static int randomValue(int n) { 
74.         return (int) (Math.random() * (n * n * n - 1) + 1); 
75.     } 
76.  
77.     /** 
78.      * 改写的合并排序，根据数组P中定义的优先级决定顺序。 
79.      * @param array 
80.      * @return 
81.      */ 
82.     private static int[] mergeSort(int[] array, int[] keyArray) { 
83.         // 如果数组的长度大于1，继续分解数组 
84.         if (array.length > 1) { 
85.             int leftLength = array.length / 2; 
86.             int rightLength = array.length - leftLength; 
87.             // 创建两个新的数组 
88.             int[] left = new int[leftLength]; 
89.             int[] right = new int[rightLength]; 
90.             // 创建两个新的key数组 
91.             int[] leftKey = new int[leftLength]; 
92.             int[] rightKey = new int[rightLength]; 
93.             // 将array中的值分别对应复制到两个子数组中 
94.             for (int i = 0; i < leftLength; i++) { 
95.                 left[i] = array[i]; 
96.                 leftKey[i] = keyArray[i]; 
97.             } 
98.             for (int i = 0; i < rightLength; i++) { 
99.                 right[i] = array[leftLength + i]; 
100.                 rightKey[i] = keyArray[leftLength + i]; 
101.             } 
102.             // 递归利用合并排序，排序子数组 
103.             left = mergeSort(left,leftKey); 
104.             right = mergeSort(right,rightKey); 
105.             // 设置初始索引 
106.             int i = 0; 
107.             int j = 0; 
108.             for (int k = 0; k < array.length; k++) { 
109.                 // 如果左边数据索引到达边界则取右边的值 
110.                 if (i == leftLength && j < rightLength) { 
111.                     array[k] = right[j]; 
112.                     j++; 
113.                     // 如果右边数组索引到达边界，取左数组的值 
114.                 } else if (i < leftLength && j == rightLength) { 
115.                     array[k] = left[i]; 
116.                     i++; 
117.                     // 如果均未到达边界，则根据优先级数组中定义的顺序排序
118.                 } else if (i < leftLength && j < rightLength) { 
119.                     if (leftKey[i] > rightKey[j]) { 
120.                         array[k] = right[j]; 
121.                         j++; 
122.                     } else if (leftKey[i] < rightKey[j]){ 
123.                         array[k] = left[i]; 
124.                         i++; 
125.                     }  
126.                 } 
127.             } 
128.         } 
129.         return array; 
130.     } 
131.      
132.     private static void printArray(int[] array) { 
133.         for (int i : array) { 
134.             System.out.print(i + " "); 
135.         } 
136.     } 
137.  
138. } 

     本文转自mushiqianmeng 51CTO博客，原文链接：http://blog.51cto.com/mushiqianmeng/734384，如需转载请自行联系原作者