排序算法之快速排序(JAVA)

排序过程
在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边，大于此数的放在右边。排好该元素后，再对该元素两边递归调用快速排序，重复这个过程。

排序的各项指标
平均时间复杂度：O(NlogN)
最坏时间复杂度：O(N^2)
空间复杂度：O(logN)
是否稳定：不稳定

排序实现

在这里插入代码片
public static void quickSort(int[] arr) {
    if (arr == null || arr.length == 0) {
        return;
    }
    quickSort(arr, 0 , arr.length - 1);
}

public static void quickSort(int[] arr, int l, int r) {
    if (l < r) {
        swap(arr, l + (int)(Math.random() * (r - l + 1)), r);
        int[] p = partition(arr, l, r);
        quickSort(arr, l, p[0] - 1);
        quickSort(arr, p[1] + 1, r);
    }
}

public static int[] partition(int[] arr, int l, int r) {
    int less = l - 1;
    int more = r;

    while (l < more) {
        if (arr[l] < arr[r]) {
            swap(arr, ++less, l++);
        } else if (arr[l] > arr[r]) {
            swap(arr, --more, l);
        } else {
            l++;
        }
    }
    swap(arr, more, r);
    return new int[]{less + 1, more};
}

public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}