用java写一个快速排序
时间: 2024-03-09 14:17:46 浏览: 13
下面是一个用Java实现的快速排序算法:
```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[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {10, 80, 30, 90, 40, 50, 70};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
```
在该实现中,我们首先定义了一个`quickSort()`方法,该方法接收一个整型数组和两个整型参数`left`和`right`。`left`和`right`分别表示要排序的数组的左边和右边的索引。
在`quickSort()`方法中,我们首先检查`left`和`right`是否相等。如果它们相等,则说明要排序的数组只有一个元素,因此我们无需进行任何操作。否则,我们将数组分为两部分,使左半部分的元素小于右半部分的元素。我们使用`partition()`方法来实现这一点。
在`partition()`方法中,我们选择数组的最后一个元素作为枢轴元素(pivot)。我们使用两个指针`i`和`j`来遍历数组。`i`指针指向左半部分的最后一个元素,`j`指针指向当前遍历到的元素。如果当前遍历到的元素小于枢轴元素,则将`i`指针向右移动一位,并交换`i`和`j`指针所指向的元素。最后,我们将枢轴元素和`i+1`位置的元素交换,使枢轴元素排在左半部分的最后一个位置。
最后,我们在`main()`方法中定义了一个整型数组,并调用`quickSort()`方法来对其进行排序。我们使用`Arrays.toString()`方法将排序后的数组打印出来。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)