用java实现快速排序

快速排序是一种常用的排序算法，它通过选择一个基准元素，将待排序序列划分为两个子序列，其中一个子序列的元素都小于等于基准元素，另一个子序列的元素都大于等于基准元素，然后递归地对子序列进行排序，最终得到有序序列。

以下是使用Java实现快速排序的示例代码：

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 6, 8, 1, 9, 4, 7};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            if (arr[i] <= pivot) {
                i++;
            } else if (arr[j] > pivot) {
                j--;
            } else {
                swap(arr, i, j);
            }
        }
        swap(arr, left, j);
        return j;
    }

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

在主函数中，我们定义了一个待排序的整型数组，然后调用快速排序函数进行排序，并输出排序结果。

快速排序函数的参数包括待排序数组、左边界和右边界。在函数内部，我们首先判断左边界是否小于右边界，如果是，则进行快速排序操作。我们选择数组的第一个元素作为基准元素，然后通过partition函数将数组划分为两个子序列。接着对左右子序列分别进行递归排序操作。

partition函数的作用是将待排序序列划分为两个子序列，其中一个子序列的元素都小于等于基准元素，另一个子序列的元素都大于等于基准元素。它的参数包括待排序数组、左边界和右边界。在函数内部，我们首先选择数组的第一个元素作为基准元素，然后定义两个指针i和j，分别指向数组的左右两端。接着，我们不断移动指针i和j，直到它们相遇或者i指向的元素大于基准元素、j指向的元素小于等于基准元素。如果i和j没有相遇，则交换i和j指向的元素。最后，交换基准元素和j指向的元素，并返回j的位置。

swap函数的作用是交换数组中两个元素的值。它的参数包括待交换的数组和两个元素的下标。在函数内部，我们使用一个临时变量temp来保存arr[i]的值，然后将arr[i]赋值为arr[j]，最后将arr[j]赋值为temp。