/**
 * @Description: 随机快排，时间复杂度O(N*logN)，空间复杂度O(logN)
 * @author: harold
 * @date: 2021年06月15日 14:35
 */
public class RandomQuickSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        sortProcess(arr, 0, arr.length - 1);
    }

    private static void sortProcess(int[] arr, int L, int R) {
        if (L < R) {
            swap(arr, L + (int)((R - L + 1) * Math.random()), R);
            int[] p = partition(arr, L, R);
            sortProcess(arr, L, p[0] - 1);
            sortProcess(arr, p[1] + 1, R);
        }

    }

    private static int[] partition(int[] arr, int L, int R) {
        int less = L - 1;
        int more = R + 1;
        int num = arr[R];
        while (L < more) {
            if (arr[L] < num) {
                swap(arr, ++less, L++);
            } else if (arr[L] > num) {
                swap(arr, L, --more);
            } else {
                L++;
            }
        }
        return new int[]{less + 1, more - 1};
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}