Java编程：快速排序函数实现-使用递归实现快速排序

快速排序是一种高效的排序算法，也是经典的分治算法的应用之一。快速排序的基本思想是通过一趟排序将待排序序列分割成两部分，一部分所有元素小于基准值，一部分所有元素大于基准值，然后递归地对两部分序列进行快速排序。本文将介绍如何使用递归实现快速排序。

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

1. 选择一个基准元素，通常选择第一个元素或者随机选择一个元素。

2. 将序列分成两个子序列，其中第一个子序列的元素都小于或等于基准元素，第二个子序列的元素都大于基准元素。

3. 对于两个子序列分别进行快速排序。

4. 合并两个排好序的子序列。

代码实现如下：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        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);
    }
}

上面的代码实现了递归快速排序的核心逻辑，其中left表示待排序序列的起始位置，right表示待排序序列的结束位置，pivot表示基准元素。

在代码中，使用双指针i和j分别从序列的两端开始向中间扫描，当i指向的元素大于等于基准元素时，停止移动i；当j指向的元素小于等于基准元素时，停止移动j。然后交换arr[i]和arr[j]的值。重复上述操作，直到i=j。

最后，将基准元素赋值给arr[i]，然后对左半部分和右半部分进行递归快速排序。

示例：

int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); //[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

本文介绍了如何使用递归实现快速排序算法。通过对递归快排的理解和实现，可以更好地理解分治算法的思想，也可以更好的理解算法的本质。