两边扔 ;双边指针
public class QuickSorting {
private static int doublePointerSwap(int[] arr, int startIndex,int endIndex){
int pivot = arr[startIndex];
int leftPoint = startIndex;
int rightPoint = endIndex;
while (leftPoint < rightPoint) {
/**
* 因为是小->大，所以下面两个while不能交换位置，第一个while必须是找到小值
*/
//从右往左找，知道找到比pivot小的值的下标
while (leftPoint < rightPoint && arr[rightPoint] >= pivot) {
rightPoint--;
}
//从左往右找，直到找到比pivot大的值的下标
while (leftPoint < rightPoint && arr[leftPoint] <= pivot) {
leftPoint++ ;
}
//找到后，交换两者的值
if (leftPoint < rightPoint) {
int temp = arr[leftPoint];
arr[leftPoint] = arr[rightPoint];
arr[rightPoint] = temp;
}
}
//一轮完毕后，双边指针重合
arr[startIndex] = arr[leftPoint];
arr[rightPoint] = pivot;
//返回分界值所在的标
return leftPoint;
}
public static void quickSort(int[] arr, int startIndex,int endIndex) {
if (startIndex < endIndex) { //if 必须要有 不然没有循环退出条件
int delimiterIndex = doublePointerSwap(arr, startIndex, endIndex);
quickSort(arr,startIndex,delimiterIndex-1);
quickSort(arr,delimiterIndex+1,endIndex);
}
}
public static void main(String[] args) {
int[] arr = {101,34,39,1,-1,3,1,90,123,10};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
