用java语言写一个快速排序法
时间: 2023-12-29 18:51:43 浏览: 25
好的,以下是Java语言实现的快速排序算法代码:
```
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && arr[i] < pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i <= j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
int tmp = arr[left];
arr[left] = arr[j];
arr[j] = tmp;
return j;
}
}
```
以上代码中,`quickSort` 方法接收一个待排序的数组 `arr`,以及数组的左右边界 `left` 和 `right`。它首先判断左右边界是否合法(`left` 必须小于 `right`),然后调用 `partition` 方法进行分区操作,将数组划分为左右两个部分,分别递归调用 `quickSort` 方法对左右两个部分进行排序。
`partition` 方法接收一个待分区的数组 `arr`,以及数组的左右边界 `left` 和 `right`。它首先选取数组的第一个元素作为基准值 `pivot`,然后用两个指针 `i` 和 `j` 分别从左右两端开始扫描数组。指针 `i` 找到第一个大于等于 `pivot` 的元素,指针 `j` 找到第一个小于等于 `pivot` 的元素,然后交换这两个元素。当指针 `i` 和 `j` 相遇时,将基准值 `pivot` 与指针 `j` 所指向的元素交换位置,完成一次分区操作,并返回分区后基准值的下标。