java模拟随机快速排序RQS

/**
* 测试随机快速排序
*/
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]

   }
}