java快速排序代码（java中快速排序算法）

Java快速排序

简介

快速排序是一种高效的排序算法，以其平均时间复杂度为 O(n log n) 而闻名。它使用分治技术将数组划分为较小的子数组，然后递归地对子数组进行排序。

快速排序算法

步骤：

1.

选择一个枢纽元素。

通常选择数组的第一个或最后一个元素。 2.

将数组划分为两个子数组。

将所有小于枢纽元素的元素放在左侧子数组中，所有大于或等于枢纽元素的元素放在右侧子数组中。 3.

对两个子数组递归地应用快速排序。

4.

连接已排序的子数组。

代码实现

```java public class QuickSort {public static void sort(int[] arr, int low, int high) {if (low < high) {int partitionIndex = partition(arr, low, high);// 对左子数组进行快速排序sort(arr, low, partitionIndex - 1);// 对右子数组进行快速排序sort(arr, partitionIndex + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = (low - 1); // 指向小于枢纽元素的元素的索引for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交换 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将枢纽元素放在其正确的位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};sort(arr, 0, arr.length - 1);System.out.println("排序后的数组：");for (int i : arr) {System.out.print(i + " ");}} } ```

时间复杂度

快速排序的平均时间复杂度为 O(n log n)。然而，在最坏的情况下，当数组已经有序或逆序时，其时间复杂度将退化为 O(n^2)。

空间复杂度

快速排序的空间复杂度为 O(log n)，因为它使用递归调用栈来存储子数组。

优点

高效的平均时间复杂度

原地排序，不需要额外的空间

可以并行化

缺点

最坏情况下时间复杂度为 O(n^2)

对已经有序或逆序的数组效率较低