使用Java写一个快速排序
时间: 2023-09-07 07:12:34 浏览: 57
以下是使用Java编写的快速排序代码:
```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); // 对基准值右边的子数组进行快速排序
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 选择第一个元素作为基准值
int i = left;
int 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;
}
public static void main(String[] args) {
int[] arr = {5, 9, 3, 6, 1, 8, 7, 2, 4};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
```
在上面的代码中,`quickSort`方法接收一个整型数组和两个整数`left`和`right`作为参数,表示要对数组中从下标`left`到下标`right`的元素进行排序。
在`quickSort`方法中,首先判断`left`和`right`是否相等,如果相等则表示只有一个元素,不需要排序,直接返回。如果`left`小于`right`,则调用`partition`方法获取基准值的下标,然后递归调用`quickSort`方法对基准值左边的子数组和右边的子数组进行排序。
`partition`方法选择第一个元素作为基准值,然后从数组的两端开始向中间查找,找到第一个小于基准值的元素和第一个大于基准值的元素,然后交换它们的位置,一直查找直到两个指针相遇。最后将基准值放到最终的位置上,然后返回基准值的下标。
在`main`方法中,创建一个整型数组并初始化,然后调用`quickSort`方法对数组进行排序,并输出排序结果。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)