如何使用java实现快速排序
时间: 2023-03-13 15:35:42 浏览: 57
快速排序是一种分治算法,其基本思想是:
1. 从数列中选择一个元素,作为基准元素。
2. 所有小于基准元素的元素,都放在基准元素的左边;所有大于基准元素的元素,都放在基准元素的右边。
3. 递归地对基准元素左边和右边的两个子数列,进行快速排序。
实现方法如下:
```java
class QuickSort {
public 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 int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选择最右边的元素作为基准元素
int i = left; // 从左往右扫描,找到比基准元素小的元素
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
swap(arr, i, j); // 交换i和j
i++;
}
}
swap(arr, i, right); // 将基准元素放在中间,左边的元素都比它小,右边的元素都比它大
return i; // 返回分区点
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```