java的快速排序怎么写?
时间: 2023-03-02 14:08:37 浏览: 51
Java中的快速排序通常使用递归的方式实现。下面是一种可能的实现方式:
```java
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); // 对右半部分递归排序
}
}
private 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];
i++;
}
while (i < j && arr[i] < pivot) { // 从左往右找第一个大于等于枢纽元的元素
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot; // 将枢纽元放到正确的位置
return i;
}
```
在快速排序中,每次选择一个枢纽元(pivot),将数组分为两部分,一部分小于等于pivot,另一部分大于pivot。然后对这两部分递归进行排序,直到每个部分只有一个元素或为空。在上面的实现中,我们选择了第一个元素作为枢纽元,但实际上也可以选择随机位置或者数组中的中位数等作为枢纽元。