java的快速排序怎么写?
时间: 2023-03-03 20:03:24 浏览: 51
Java的快速排序可以按照以下步骤实现:
1. 选择一个枢轴元素pivot(通常选择数组的第一个元素)。
2. 把数组分成两部分,小于等于pivot的元素放在左边,大于pivot的元素放在右边。
3. 对左右两部分分别递归地执行步骤1和步骤2,直到数组只剩下一个元素或为空。
下面是Java代码实现:
```java
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right); // 选取枢轴元素并对数组进行划分
quickSort(arr, left, pivotIndex - 1); // 对左半部分递归执行快速排序
quickSort(arr, pivotIndex + 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];
}
// 从左往右扫描,找到第一个大于等于枢轴元素的元素
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot; // 把枢轴元素放到正确的位置
return i;
}
```
在使用该方法时,可以调用 `quickSort(arr, 0, arr.length - 1)` 来对整个数组进行排序。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)