Java函数：如何使用递归实现快速排序

快速排序是一种经典的排序算法，它的核心思想是分治法。它是一种原地排序算法，不需要额外的空间。

快速排序算法的主要步骤如下：

1. 选定一个元素作为基准值（pivot），一般选择 个元素或者最后一个元素。

2. 将序列中的元素分为左右两个部分，左边的元素都小于等于基准值，右边的元素都大于等于基准值。

3. 递归地对左右两个部分进行排序。

使用递归实现快速排序的函数如下：

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }

    int i = left, j = right, pivot = arr[left];
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i++] = arr[j];
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j--] = arr[i];
        }
    }
    arr[i] = pivot;

    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

函数接受三个参数，分别为要排序的数组、要排序的区间左端点、要排序的区间右端点。

函数首先判断左右端点是否相等或者左端点大于右端点，如果是的话就直接返回。

然后选定数组的 个元素作为基准值，进行一趟快排操作，将小于等于基准值的元素移动到数组的左边，大于等于基准值的元素移动到数组的右边。

最后递归地对左右两个部分进行排序。

使用递归实现快速排序的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。因为快排是原地排序算法，所以空间复杂度只与递归栈的深度有关，即 O(logn)。