/**
 * @author CLY
 * 快速排序
 */
public class MyQuickSort {
    /**
     * 对待排数组排序（升序）
     * @param arr 待排数组
     * @param pivot 枢轴在待排数组中的起始位置（排序起始位）
     * @param end 本次快排的结束位（排序结束位）
     */
    public static void sort(int[] arr,int pivot,int end) {
        int tmp_pivot = pivot;
        int tmp_end = end;
        
        //为true时pivot在数组左边，为false时在右边
        boolean flag = true;
        //整个过程是end往pivot逼近的过程
        while (tmp_pivot!=tmp_end) {
            if (flag) {//pivot在左边
                while (tmp_pivot<tmp_end) {
                    //如果成立，则枢轴被换到右边，比枢轴小的数被换到左边 
                    if (arr[tmp_pivot]>arr[tmp_end]) {
                        int tmp = arr[tmp_pivot];
                        arr[tmp_pivot] = arr[tmp_end];
                        arr[tmp_end] = tmp;
                        
                        int tmp_index = tmp_pivot;
                        tmp_pivot = tmp_end;
                        tmp_end = tmp_index;
                        tmp_end++;
                        break;
                    }else {//查找上一个右边的数，看是否比枢轴小
                        tmp_end--;
                    }
                }
                flag = false;
            }else {//pivot在右边
                while (tmp_pivot>tmp_end) {
                    //如果成立，则枢轴被换到左边，比枢轴大的数被换到左边 
                    if (arr[tmp_pivot]<arr[tmp_end]) {
                        int tmp = arr[tmp_pivot];
                        arr[tmp_pivot] = arr[tmp_end];
                        arr[tmp_end] = tmp;
                        
                        int tmp_index = tmp_pivot;
                        tmp_pivot = tmp_end;
                        tmp_end = tmp_index;
                        tmp_end--;
                        break;
                    }else {//查找下一个左边的数，看是否比枢轴大
                        tmp_end++;
                    }
                }
                flag = true;
            }
        }
        //此时枢轴左边的数都比它小，右边的数都比它大。
        //如果整个待排数组长度小于2，就表示已经排到底了。
        if (end-pivot<2) {
            return;
        }
        //如果当前枢轴在起始点的右边，就表示枢轴左边有值，可以对左边进行快排
        if (tmp_pivot>pivot) {
            sort(arr, pivot, tmp_pivot-1);//对左边的数进行快排
        }
        //如果当前枢轴在结束点的左边，就表示枢轴右边有值，可以对右边进行快排
        if (tmp_pivot<end) {
            sort(arr, tmp_pivot+1, end);//对右边的数进行快排
        }
    }
}