i和j的取值 与 x取左右边界有关
如果x的值包含右边界,那么递归时认为i取不到左边界;
同理如果x的值包含左边界,那么递归时认为j取不到右边界。
// 快速排序算法模板(选用)
public static void quickSort(int[] q,int l,int r){
if(l>=r)return;
int i = l-1, j = r+1, x = q[l+r>>1]; //2. 因为j不能取到右边界,所以取下界(q[l]或q[l+r>>1])
while(i<j){
do i++; while(q[i]<x);
do j--; while(q[j]>x);
if(i<j){
int tmp = q[i];
q[i]=q[j];
q[j]=tmp;
}
}
quickSort(q,l,j); //1. j不能取到右边界,若取到则会无限递归下去 此时q[j]<=x,q[j+1]>=x而x是2.中定义的
quickSort(q,j+1,r);
}
其它模板
// 快速排序算法模板(其他)
public static void quickSort(int[] q,int l,int r){
if(l>=r)return;
int i = l-1, j = r+1, x = q[l+r+1>>1]; //2. 因为i不能取到左边界,所以取上界(q[r]或q[l+r+1>>1])
while(i<j){
do i++; while(q[i]<x);
do j--; while(q[j]>x);
if(i<j){
int tmp = q[i];
q[i]=q[j];
q[j]=tmp;
}
}
quickSort(q,l,i-1);
quickSort(q,i,r); //1. i不能取到左边界,若取到则会无限递归下去 此时q[i-1]<=x,q[i]>=x,而x是2.中定义的
}
输入输出
public static void main(String[] args) throws Exception{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] q = new int[n];
String[] strs = br.readLine().split(" ");
for(int i=0;i<q.length;i++)q[i]=Integer.parseInt(strs[i]);
quickSort(q,0,q.length-1);
for(int i=0;i<q.length;i++){
if(i==q.length-1)System.out.print(q[i]);
else System.out.print(q[i]+" ");
}
}