java快速排序模板
时间: 2024-03-10 10:41:44 浏览: 23
Java快速排序是一种常用的排序算法,它基于分治的思想,通过将数组分成较小的子数组来进行排序。以下是Java快速排序的一个常见实现模板:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high); // 将数组分区,并获取基准元素的索引
// 递归地对基准元素左右两侧的子数组进行排序
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为基准元素
int i = low + 1; // 从基准元素的下一个位置开始遍历
int j = high;
while (i <= j) {
if (arr[i] <= pivot) {
i++;
} else if (arr[j] > pivot) {
j--;
} else {
swap(arr, i, j); // 交换arr[i]和arr[j]
}
}
swap(arr, low, 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`方法来对一个整型数组进行快速排序。其中,`low`表示数组的起始索引,`high`表示数组的结束索引。