用Java写下快速排序

快速排序是一种高效的排序算法，其时间复杂度为O(nlogn)。以下是用Java实现快速排序的代码：

public class QuickSort {

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);
    }
}

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

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

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

}

在这个实现中，我们首先定义了一个quickSort方法，该方法接收一个int数组、左边界和右边界作为参数。如果左边界小于右边界，则进行以下操作：

1. 选择数组中的最后一个元素作为枢轴（pivot）。
2. 定义一个指针i，初始值为left-1。
3. 遍历数组中left到right-1的元素，如果元素小于枢轴，则将指针i右移一位，并交换元素i和元素j。
4. 遍历结束后，交换i+1和right位置上的元素，使枢轴元素归位。返回i+1作为枢轴的位置。
5. 对左边和右边的子数组分别递归调用quickSort方法。

在main方法中，我们定义了一个测试数组，调用quickSort方法进行排序，并输出结果。

输出结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]