题解 | #排序# 快速排序_双指针法

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        quickSort(arr);
        return arr;
    }

    private void quickSort(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        quickSort(low, high ,arr);
    }

    private void quickSort(int low, int high, int[] arr) {
        //若low == high，则该轮快排终止。
        if (low >= high) {
            return;
        }
        int i = low;
        int j = high;
        int pivot = arr[low]; //pivot随意设置

        while (i < j) {
            //从右往左找比pivot小的数
            while (arr[j] >= pivot && i < j) {
                j--;
            }
            //从左往右找比pivot大的数
            while(arr[i] <= pivot && i < j) {
                i++;
            }
            //若左、右指针未相遇，说明往左、往右均找到，此时交换左、右指针元素
            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        //交换相遇点与pivot处元素
        arr[low] = arr[i];
        arr[i] = pivot;
        //此时，以pivot为界，数组被分为左、右两部分，分别对其递归快排即可
        quickSort(low, i-1, arr);
        quickSort(i+1, high, arr);
    }
}