java快速排序
时间: 2023-06-21 19:16:18 浏览: 40
快速排序是一种基于分治思想的排序算法,它使用递归的方式将一个大问题分解为多个小问题,然后通过合并小问题的解来解决大问题。下面是 Java 实现快速排序的代码:
```java
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
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 pivotValue = arr[left];
int i = left + 1;
int j = right;
while (true) {
while (i <= j && arr[i] < pivotValue) {
i++;
}
while (i <= j && arr[j] > pivotValue) {
j--;
}
if (i >= j) {
break;
}
swap(arr, i, j);
}
swap(arr, left, j);
return j;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
这里的 `quickSort(int[] arr)` 方法是公开接口,它通过调用 `quickSort(int[] arr, int left, int right)` 方法来实现快速排序。在 `quickSort(int[] arr, int left, int right)` 方法中,我们选择数组的第一个元素作为枢轴元素,然后使用左右指针分别从左右两侧开始扫描数组,并且交换左右指针所指元素的位置,直到左指针大于右指针时退出循环。最后我们将枢轴元素和右指针所指元素的位置交换,然后返回右指针的位置,这个位置就是枢轴元素最终的位置。在递归调用快速排序时,我们分别对左半部分和右半部分进行排序。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)