问题描述：
实现对数组的普通快速排序与随机快速排序
实验要求：
（1）实现上述两个算法
（2）统计算法的运行时间
（3）分析性能差异，作出总结
代码：
一：普通快速排序
public class QuickSort1 {
public static void QuickSort(int []A,int l,int r){
int temp;
int i = l;
int j = r;
if(l<r){
temp = A[i];
while(i != j){
while(i<j && A[j] >= temp){
--j;
}
A[i] = A[j];
while(i<j && A[i] <= temp){
++i;
}
A[j] = A[i];
}
A[i] = temp;
QuickSort(A, l, i-);
QuickSort(A, i+, r);
}
}
二：随机快速排序
public static void exchange(int[] array,int a,int b){
int temp = 0;
temp = array[a];
array[a] = array[b];
array[b] = temp;
}
public static int random_patition(int[] A,int left,int right){
int temp = 0;
int i = left-1;
Random random = new Random();
int k = left + random.nextInt(right - left);
exchange(A,k,right);
temp = A[right];
//找到所有比temp小的数，放在temp左边
for(int j = left ; j<right ; j++){
if(A[j] <= temp){
i++;
exchange(A,i,j);
}
}
//将枢轴放回原位
exchange(A,i+1, right);
return i+1;
}
public static void QuickSort(int[] A,int l,int r){
if(l<r){
int dot = random_patition(A, l, r);
QuickSort(A, l, dot-1);
QuickSort(A, dot+1, r);
}
}三：比较两个时间差的main函数
public static void main(String[] args){
int[] A = new int[20000];
int[] A_copy = new int[20000];
//生成两个随机数组
// System.out.println("排序之前的20000个数是：");
// Random random = new Random();
// for(int i = 0; i<A.length;i++){
// A[i] = (int)random.nextInt(100000);
// A_copy[i] = A[i];
// System.out.print(A[i]+" ");
// if(i%10 == 0&&i!=0){
// System.out.print("\n");
// }
// }
//生成两个1-20000的有序数组，目的：比较当数组有序时哪个排序速度快
for(int i = 0;i<A.length;i++){
A[i] = i;
A_copy[i] = i;
}
//普通快速排序算法
Date before1 = new Date();
long before1_QuickSort = before1.getTime();
QuickSort(A,0,1999);
Date after1 = new Date();
long after1_QuickSort = after1.getTime();
long time1 = after1_QuickSort - before1_QuickSort;
//随机快速排序算法
Date before2 = new Date();
long before2_QuickSort = before2.getTime();
QuickSort2.QuickSort(A_copy, 0, 1999);
Date after2 = new Date();
long after2_QuickSort = after2.getTime();
long time2 = after2_QuickSort - before2_QuickSort;
System.out.println("\n普通快速排序之后的20000个数是:");
for(int k = 0;k<A.length;k++){
System.out.print(A[k]+" ");
if(k%10 == 0&&k!=0){
System.out.print("\n");
}
}
System.out.println("\n普通快速排序算法运行时间："+time1);
System.out.println("随机快速排序算法运行时间："+time2);
System.out.println("相差"+(time1-time2));
}