java实现快速排序

 图解

快速排序是一种常见的排序算法，它通过选取一个基准元素，将待排序的数组划分为两个子数组，一个子数组中的元素都小于基准元素，另一个子数组中的元素都大于基准元素。然后递归地对子数组进行排序，直到子数组的长度为1或0。

快速排序的步骤如下：

1. 选择一个基准元素，通常选择数组的第一个元素。
2. 将数组划分为两个子数组，左边的子数组中的元素都小于基准元素，右边的子数组中的元素都大于基准元素。可以使用双指针法实现。
3. 对左边的子数组递归地应用上述步骤，对右边的子数组递归地应用上述步骤，直到子数组的长度为1或0。

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)，其中n为待排序数组的长度。

快速排序是一种高效的排序算法，以下是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); // 递归排序右子数组}}public static int partition(int[] arr, int left, int right) {int pivot = arr[left];   // 将左边第一个元素选为基准值while (left < right) {// 从右边开始找到第一个小于基准值的元素while (left < right && arr[right] >= pivot) {right--;}// 将小于基准值的元素放到左边arr[left] = arr[right];// 从左边开始找到第一个大于基准值的元素while (left < right && arr[left] <= pivot) {left++;}// 将大于基准值的元素放到右边arr[right] = arr[left];}arr[left] = pivot;  // 将基准值放到中间return left;    // 返回基准值的位置}public static void main(String[] args) {int[] arr = {6, 1, 3, 9, 2, 7, 4, 8, 5};quickSort(arr, 0, arr.length - 1);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}

快速排序的时间复杂度为O(nlogn)。