package moshi;
public class Main {
public static void main(String[] args) {
Main m = new Main();
int[] arr ={3,4,5,1,2};
m.快速排序(arr);
System.out.println();
}
public void 快速排序(int[] arr){
quickSort(arr,0,arr.length-1);
}
public void quickSort(int[] arr,int start,int end){
if(start<end){
int partition = partition(arr,start,end);
quickSort(arr,start,partition-1);
quickSort(arr,partition+1,end);
}
}
public int partition(int[] arr,int start,int end){
int temp = arr[start];
while(start < end){
//找到比temp小的元素的下标，并交换这个元素与temp,以此循环使比temp小的都在temp左边
while(start < end && arr[end] >= temp){
end--;
}
swap(arr,start,end);
//找到比temp大的元素的下标，并交换这个元素与temp,以此循环使比temp大的都在temp右边
while(start < end && arr[start] <= temp){
start++;
}
swap(arr,start,end);
}
return start;
}
private void swap(int[] arr,int start,int end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
