public class QuicklySort {
    public  void quicklySort(int[] arr, int base, int tail){
        /*
         * 快速排序的核心:选取一个参考点,然后操作此数组,得到参考点的值左边的值全都比参考点值小,右边的值全都比参考点的大
         * 然后将左边作一个子序列,右边看作另外一个子序列([XXXXXXXXX 参考值 XXXXXXXXXXXXXXXXXXXX]),然后分别对这两个子序列
         * 做相同的事情(递归),直到子序列为长度1或者0(小于2个).[XXXXX参考值]-->此时右边子序列长度为0,[XXXXX参考值X]-->右边子序列长度为1;
         *
         * 在这个程序中,将原始数组操作的方法是:
         * 1.设一个left索引点,从左边开始找,找到大于参考点值的记录为left(此时left左边的都比参考点小)#注:left不能超过此次要排序的片段的最右边对吧?;
         *    同时设一个right索引点,从右边开始找,找到小于参考点的记录为right(此时tight右边的都比参考的大)#注:right不能超过此次要排序的片段的最左边对吧?;
         *    (如果想把与参考值相同的都一口气都放在左边,在则left遇到相等就跳过,right遇到相等就记录)别把全部相等放右边,因为这样第一个参考点必定会被left记录,虽然这总结果换过来一定是小于等于参考点的新参考点,不会报错,但是这样做会使得左子序列变短,导致降低排序效率
         *    (也可以把参考值相同的不管,都跳过,因为既可以当做大于参考值的,也可做小于参考值的) 这种效率应该最高
         * 2.如果left<right,则交换 left和right指向的值. 然后继续寻找(重复第一步)
         * 直到left>right,(不会出现left等于right的情况的--),因为不存在一个值既小于又大于参考值,与参考值相等时候,我们也会保证其中一个跳走,或者一起跳走
         *
         * 3.交换参考点和right的值(此时left记录的是比参考点值大的,right记录的是比参考点值小的,跟right交换则保证了左边全部小于参考值,右边全部大于)达到目的
         *
         * 4.当子序列长度大于1时候才进行递归  左边子序列(base--->right-1)         right-1>base时候就长度超过1
         *                                    右边子序列(right+1--->tail)         tail>right+1时候就长度超过1
         *
         *
         */


        int left=base; //base和tail是将传入数组的,本次递归需要排序的部分的,起始索引记录保存下来,
        int right=tail;//并且以base的值为参考点(这个点值拿来参考作用,本身要参与排序的,所以left要从过这里开始).
        int temp=0;// 交换数组中两个值用的暂存值
        
            while (left<right) {//每次交换完后,只要还满足left<right就继续找
               
                while (true) {//用死循环,在此次排序片段的范围内,找arr[left] > arr[base]的点处的索引,记录下left
                    if (left < tail && arr[left] <= arr[base]) {
                        left++;
                    } else {
                        break;
                    }
                }
               
                while (true) {//用死循环,在此次排序片段的范围内,找arr[right] <arr[base]的点处的索引,记录下
                    if (right > base && arr[right] >= arr[base]) {
                        right--;
                    } else {
                        break;
                    }
                }
               
                if (left < right) {  //记录下来的left小于right时候交换值
                    temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
            }
            
            //交换base 和right
            temp = arr[base];
            arr[base] = arr[right];
            arr[right] = temp;
            if (right - 1 > base) {//子序列长度超过1
                quicklySort(arr, base, right - 1);
            }
            if (right + 1 <tail) {//子序列长度超过1
                quicklySort(arr, right + 1, tail);
            }
        }
}

public class QuicklySort {
    public  void quicklySort(int[] arr, int base, int tail){
        /*
         * 快速排序的核心:选取一个参考点,然后操作此数组,得到参考点的值左边的值全都比参考点值小,右边的值全都比参考点的大
         * 然后将左边作一个子序列,右边看作另外一个子序列([XXXXXXXXX 参考值 XXXXXXXXXXXXXXXXXXXX]),然后分别对这两个子序列
         * 做相同的事情(递归),直到子序列为长度1或者0(小于2个).[XXXXX参考值]-->此时右边子序列长度为0,[XXXXX参考值X]-->右边子序列长度为1;
         *
         * 在这个程序中,将原始数组操作的方法是:
         * 1.设一个left索引点,从左边开始找,找到大于参考点值的记录为left(此时left左边的都比参考点小)#注:left不能超过此次要排序的片段的最右边对吧?;
         *    同时设一个right索引点,从右边开始找,找到小于参考点的记录为right(此时tight右边的都比参考的大)#注:right不能超过此次要排序的片段的最左边对吧?;
         *    (如果想把与参考值相同的都一口气都放在左边,在则left遇到相等就跳过,right遇到相等就记录)别把全部相等放右边,因为这样第一个参考点必定会被left记录,虽然这总结果换过来一定是小于等于参考点的新参考点,不会报错,但是这样做会使得左子序列变短,导致降低排序效率
         *    (也可以把参考值相同的不管,都跳过,因为既可以当做大于参考值的,也可做小于参考值的) 这种效率应该最高
         * 2.如果left<right,则交换 left和right指向的值. 然后继续寻找(重复第一步)
         * 直到left>right,(不会出现left等于right的情况的--),因为不存在一个值既小于又大于参考值,与参考值相等时候,我们也会保证其中一个跳走,或者一起跳走
         *
         * 3.交换参考点和right的值(此时left记录的是比参考点值大的,right记录的是比参考点值小的,跟right交换则保证了左边全部小于参考值,右边全部大于)达到目的
         *
         * 4.当子序列长度大于1时候才进行递归  左边子序列(base--->right-1)         right-1>base时候就长度超过1
         *                                    右边子序列(right+1--->tail)         tail>right+1时候就长度超过1
         *
         *
         */


        int left=base; //base和tail是将传入数组的,本次递归需要排序的部分的,起始索引记录保存下来,
        int right=tail;//并且以base的值为参考点(这个点值拿来参考作用,本身要参与排序的,所以left要从过这里开始).
        int temp=0;// 交换数组中两个值用的暂存值
        
            while (left<right) {//每次交换完后,只要还满足left<right就继续找
               
                while (true) {//用死循环,在此次排序片段的范围内,找arr[left] > arr[base]的点处的索引,记录下left
                    if (left < tail && arr[left] <= arr[base]) {
                        left++;
                    } else {
                        break;
                    }
                }
               
                while (true) {//用死循环,在此次排序片段的范围内,找arr[right] <arr[base]的点处的索引,记录下
                    if (right > base && arr[right] >= arr[base]) {
                        right--;
                    } else {
                        break;
                    }
                }
               
                if (left < right) {  //记录下来的left小于right时候交换值
                    temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
            }
            
            //交换base 和right
            temp = arr[base];
            arr[base] = arr[right];
            arr[right] = temp;
            if (right - 1 > base) {//子序列长度超过1
                quicklySort(arr, base, right - 1);
            }
            if (right + 1 <tail) {//子序列长度超过1
                quicklySort(arr, right + 1, tail);
            }
        }
}