使用java实现一个快速速排序
时间: 2024-05-15 20:15:12 浏览: 12
以下是Java实现快速排序的代码:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
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);
}
}
public 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 temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
}
```
在这个实现中,`quickSort`方法接受一个整数类型的数组和数组的左右边界。它首先检查左边界是否小于右边界,如果是,它将数组划分为两部分,并递归对它们进行排序。划分是通过调用`partition`方法完成的,该方法返回一个枢轴索引,并将数组划分为小于枢轴值的元素和大于枢轴值的元素。
在`partition`方法中,我们选择数组的第一个元素作为枢轴。我们维护两个指针`i`和`j`,它们分别指向数组的左右两端。`i`指针从左向右移动,直到它找到一个大于或等于枢轴值的元素,`j`指针从右向左移动,直到它找到一个小于或等于枢轴值的元素。然后,我们交换这两个元素,使得小于枢轴值的元素位于左侧,大于枢轴值的元素位于右侧。重复此过程直到`i`和`j`相遇。最后,我们将枢轴值移到正确的位置,并返回它的索引。
这个实现的时间复杂度为O(nlogn),空间复杂度为O(logn)。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)
![](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)