public class QuickSort {
public static void quickSort(int[] arr, int low, int high){
if (low >= high){
return;
}
//退出条件是左端哨兵在右端哨兵的右边。

int temp = arr[low]; //temp就是基准位
int left = low; //左端哨兵位置
int right =high; //右端哨兵位置
int t; //交换数据的临时变量
//循环条件:左边哨兵位置还在右边哨兵位置的左边,右端哨兵往左走,左端哨兵往右走,直到相遇。
while ( left< right) {
//1、先看右边,依次往左递减,右端哨兵往左走。找到比基准点小的数据就停止
while (temp <= arr[right] && left < right) {
right--;
}
//2、再看左边,依次往右递增,左端哨兵往右走,找到比基准点大的数据就停止
while (temp >=arr[left] && left < right) {
left++;
}
//3、如果满足条件没有相遇则交换
if (left < right) {
t = arr[right];
arr[right] = arr[left];
arr[left] = t;
}
}
/*
最后将基准为与i和j相等位置的数字交换,i和j相遇之后就与基准点交换数据,
交换之后就完成了:基准点左边都是小于等于基准点,基准点右边都是大于等于基准点。
*/
arr[low] = arr[left];
arr[left] = temp;
//递归调用左半数组,此时就需要传入左半数组的首尾索引值,以及数组。
quickSort(arr, low, right - 1);
//递归调用右半数组
quickSort(arr, right + 1, high);

}
}