java分治法实现快速排序
时间: 2023-10-14 20:24:21 浏览: 23
这里是Java实现快速排序的分治法:
```java
public class QuickSort {
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 pivotIndex = left;
int pivotValue = arr[left];
for (int i = left + 1; i <= right; i++) {
if (arr[i] < pivotValue) {
pivotIndex++;
swap(arr, pivotIndex, i);
}
}
swap(arr, left, pivotIndex);
return pivotIndex;
}
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 = { 5, 3, 6, 8, 1, 2, 4, 7 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
```
在这个实现中,`quickSort`方法是主要的快速排序方法。如果左边的索引小于右边的索引,就说明需要进行排序。`partition`方法是用来进行分区的,它使用左边的元素作为枢轴,并将小于枢轴的元素移到左边,大于枢轴的元素移到右边。最后,`swap`方法用来交换数组中的两个元素。在`main`方法中,我们可以看到如何调用`quickSort`方法来对一个整数数组进行排序。