用java写一个快速排序
时间: 2024-03-09 12:18:57 浏览: 39
以下是使用Java实现的快速排序算法代码:
```
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right); // 获取枢轴元素的位置
quickSort(arr, left, pivot - 1); // 对左边部分进行排序
quickSort(arr, pivot + 1, right); // 对右边部分进行排序
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 选择左边第一个元素作为枢轴元素
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) { // 从右边找到第一个小于枢轴元素的位置
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] < pivot) { // 从左边找到第一个大于等于枢轴元素的位置
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot; // 把枢轴元素放到最终的位置
return i;
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 4, 5, 6, 7, 8]
}
}
```
快速排序的时间复杂度是O(nlogn),空间复杂度是O(logn)。它是一种原地排序算法,不需要额外的空间。