import java.util.*;
import static java.lang.System.*;
import java.util.stream.*;
import java.util.function.*;
public class Program {
public static void main(String[] args) {
final int Count=81,Max=51;
int[] arr=new int[Count];
Random r=new Random();
Arrays.setAll(arr,(int operand)->r.nextInt(Max));
int[] arr1=Arrays.copyOf(arr,Count);
qsort1(arr1,0,Count-1);
out.println("qsort1排序后：");
IntStream.of(arr1).forEach(e->out.printf("%d,",e));
out.println();
int[] arr2=Arrays.copyOf(arr,Count);
qsort2(arr2,0,Count-1);
out.println("qsort2排序后：");
Arrays.stream(arr2).forEach(e->out.printf("%d,",e));
out.println();
int[] arr3=Arrays.copyOf(arr,Count);
qsort3(arr3,0,Count-1);
out.println("qsort3排序后：");
Arrays.stream(arr3).forEach(e->out.printf("%d,",e));
out.println();
out.println("原数组：");
IntStream.of(arr).forEach(e->out.printf("%d,",e));
out.println();
Arrays.sort(arr);
out.println("调用类库方法Arrays.sort对原数组排序后：");
IntStream.of(arr).forEach(e->out.printf("%d,",e));
out.println();
boolean eq=true;
int[][] arrs={arr1,arr2,arr3};
for(int i=0;eq&&i<arrs.length;i++) {
eq=Arrays.equals(arr,arrs[i]);
}
out.printf("4个排序后的数组相等？%b%n",eq);
}
//3个while版
static void qsort1(int[] arr,int l,int r) {
int p,l2=l,r2=r;
if(l>=r)
return;
p=arr[l];
while(l<r) {
while(l<r&&arr[r]>p)
r--;
arr[l]=arr[r];
while(l<r&&arr[l]<=p)
l++;
arr[r]=arr[l];
}
arr[l]=p;
qsort1(arr,l2,l-1);
qsort1(arr,l+1,r2);
}
//一个for版
static void qsort2(int[] arr,int l,int r) {
int s,t;
if(l>=r)
return;
s=l;
for(int i=l+1;i<=r;i++) {
if(arr[i]<arr[l]) {
s++;
t=arr[s];
arr[s]=arr[i];
arr[i]=t;
}
}
t=arr[l];
arr[l]=arr[s];
arr[s]=t;
qsort2(arr,l,s-1);
qsort2(arr,s+1,r);
}
//非递归版
static void qsort3(int[] arr,int l,int r) {
Deque<int[]> stack;
int[] lr;
int s,t;
if(l>=r)
return;
stack=new ArrayDeque<>();
stack.push(new int[] {l,r});
while(!stack.isEmpty()) {
lr=stack.pop();
l=lr[0];
r=lr[1];
s=l;
for(int i=l+1;i<=r;i++) {
if(arr[i]<arr[l]) {
s++;
t=arr[s];
arr[s]=arr[i];
arr[i]=t;
}
}
t=arr[l];
arr[l]=arr[s];
arr[s]=t;
if(l<s-1)
stack.push(new int[] {l,s-1});
if(s+1<r)
stack.push(new int[] {s+1,r});
}
}
}