java模拟随机快速排序RQS（java怎么随机数）

/**

* 测试随机快速排序

*/

public class TestRandomQuickSort {

public static int partition(int[] arr,int low,int high){

//partition挡板 在low到high范围内设置一个挡板/支点 小于支点元素的数放在s1区 大于支点元素的数放在s2区

int ranCho = (int)((high-low+1)*Math.random()+low);

//随机选low到high之间一位作为支点

int swap ;

swap = arr[low];

arr[low] = arr[ranCho];

arr[ranCho] = swap;

//把支点元素置于首位

int pivot =arr[low];

//pivot支点 小于支点放在s1区 大于支点放在s2区

int s1r = low;

//初期s1区s2区内为空 要将支点右侧所有元素逐个和支点比较 分装进s1 s2内

for (int s2r = low+1;s2r<=high;s2r++){

//先将s2的右端扩张1位 比较这一位和支点 如果比支点大则属于s2不用动 因为已经被s2r包住了

if(arr[s2r]<pivot){

// 比支点小则属于s1 s1右端扩张1位(原属于s2)和正在比的那一位(应属于s1)交换

s1r++;

swap = arr[s1r];

arr[s1r] = arr[s2r];

arr[s2r] = swap;

}

}

//循环结束后 low至high内从左开始依次为 支点pivot s1区（low+1至s1r） s2区（s1r+1至high）

arr[low] = arr[s1r];

arr[s1r] = pivot;

//交换 将支点从low换到s1r位置 这样支点左侧为s1都比支点小 右侧为s2都比支点大

return s1r;

//把支点位置返回

}

public static void rqs(int[] array,int low,int high){

if (low<high){

int pivot = partition(array,low,high);

//用支点分出s1 s2 两个区域再往下分

rqs(array,low,pivot-1);

//s1 这里如果s1区为空 pivot=low 即rqs(array,low,low-1) 如果上面的if(low!=high)就会出问题 low-1!=low执行语句然后报错 错误总结：!=容易遗漏一些例外情况 少用

rqs(array,pivot+1,high);

//s2

}

//low==high 即此区域内只有一个元素时 void此区域排序完成

}

public static void rqs(int[] array){

//重载rqs 用于对整个数组进行排序 调用时不需要输入low=0和high=.length-1

if (array.length>1){

int pivot = partition(array,0,array.length-1);

rqs(array,0,pivot-1);

rqs(array,pivot+1,array.length-1);

}

}

public static void main(String[] args) {

int[] arr = {87,45,32,1,65,98,45,321,5,1,3,5,84,15};

rqs(arr);

System.out.println(Arrays.toString(arr));

//结果[1, 1, 3, 5, 5, 15, 32, 45, 45, 65, 84, 87, 98, 321]

}

}