public class FastSort {
//排序方法入口，传入初始边界
public static void quickSort(int arr[]) {
int right = arr.length -1; //初始边界
int left = 0;
fastSort(arr,left,right);
}
public static void fastSort(int[] arr,int left,int right) {
if(left > right) {
return;
}else {
int index = getIndex(arr,left,right); //获得分区点
fastSort(arr,left,index - 1); //对分区左侧进行递归快排
fastSort(arr,index + 1,right); //对分区右侧进行递归快排
}
}
// 选取基准元素对数组进行分区，分区点左边全部小于基准元素，右边全部大于基准元素，并返回获取分区点下标
public static int getIndex(int[] arr, int left, int right) {
int tmp = arr[left]; //首个基准
while (true) { //移动左右指针，小的往左放，大的往右放
while (left < right && arr[right] > tmp) { //left < right 每次循环左右边界需要限制好
right--;//--j移动右指针，直到寻找<=基准的元素,停止
}
while (left < right && arr[left] < tmp) {
left++;//++i，移动左指针，值到寻找到>=基准的元素，停止
}
if (left < right) {
swap(arr, left, right); //如果此次循环中i，j未相遇，则将i,j元素交换，继续前进。
//目的是将小于基准的元素都放在左边，大于基准的元素都放在右边
} else {
break; //i,j相遇，跳出循环，一轮递归结束。
}
}
swap(arr,left,right); //将基准与分区点元素进行交换，下标未动
return right; //返回分区点下标
}
//辅助交换方法-传入数组索引，交换索引上的两个元素
public static void swap(int[] arr,int i,int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
