Java用递归实现快速排序并注释每一行
时间: 2023-03-20 14:03:48 浏览: 75
答:快速排序是一种非常有效的排序算法,它使用递归来实现。以下是Java代码的实现:
// 选择基准值,并将其与数组中的最后一个元素交换位置
int pivotIndex = partition(arr, start, end);
// 递归调用快速排序,对基准值左右两边的序列分别排序
quickSort(arr, start, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, end);
// 定义划分函数,用于将一个数组划分为两部分
int partition(int[] arr, int start, int end) {
// 定义基准值
int pivot = arr[end];
// 定义小于基准值的边界
int i = start - 1;
// 遍历数组,将小于基准值的元素放到左边,大于基准值的元素放到右边
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
// 将基准值放到中间
swap(arr, i + 1, end);
// 返回基准值的索引
return i + 1;
}
// 定义交换函数,用于交换数组中两个元素的位置
void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}