Java实现高效快速排序算法

快速排序通过选择一个基准元素（pivot），然后将数组分为两部分，一部分包含所有比基准小的元素，另一部分包含所有比基准大的元素。这一过程称为分区操作，之后递归地对这两部分进行同样的操作，直到整个数组有序。

快速排序的时间复杂度通常为O(n log n)，其中n是数组长度。在最理想的情况下，每次分区都能均匀地将数组分成两个相等的部分，递归树的高度为log n。然而，在最坏的情况下，如果数组已经是有序的或者逆序的，每次分区只能将数组分成一个元素和剩余部分，此时的时间复杂度退化为O(n^2)。

下面是使用Java实现快速排序的一个示例：

```java
package com.example.sort;

import java.util.Arrays;

/**
* 快速排序算法实现
* @author Your Name
* @date 2023-09-01
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {3, 7, 2, 9, 1, 4, 6, 8, 10, 5};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}

/**
* 分区并递归排序
* @param arr 待排序数组
* @param low 起始索引
* @param high 结束索引
*/
private static void quickSort(int[] arr, int low, int high) {
if (low int partitiOnIndex= partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}

/**
* 分区操作
* @param arr 待排序数组
* @param low 起始索引
* @param high 结束索引
* @return 基准元素的位置
*/
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1); // 小于基准元素的最后一个元素的索引
for (int j = low; j // 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
i++;
// 交换元素
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;
}
}
```