我发现了这个快速排序的代码实现,我想问:代码中粗体部分是做什么的?是检查数组的左右部分是否有未排序的元素吗?
import java.util.Scanner;
public class QuickSort {
static int a[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("n = ");
int n = sc.nextInt();
System.out.println("Array: ");
a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
quickSort(0, n - 1);
System.out.println("Sorted array: ");
for (int i = 0; i < n; i++) {
System.out.print(a[i] + " ");
}
sc.close();
}
private static void quickSort(int left, int right) {
int i = left, j = right;
int pivot = a[(left + right) / 2];
while (i <= j) {
while (a[i] < pivot) {
i++;
}
while (a[j] > pivot) {
j--;
}
if (i <= j) {
swap(a, i, j);
i++;
j--;
}
}
if (left < j) {
quickSort(left, j);
}
if (i < right) {
quickSort(i, right);
}
}
private static void swap(int a[], int index1, int index2) {
int aux = a[index1];
a[index1] = a[index2];
a[index2] = aux;
}
}
字符串
我试着理解代码在做什么。
1条答案
按热度按时间m1m5dgzv1#
是否检查数组的左右部分中是否有未排序的元素?
是的就是这样
它负责在数组的左右分区上递归调用
quickSort
函数。在将数组初始划分为两个子数组(左和右)之后,对每个子数组调用
quickSort
函数以进一步排序它们。此过程递归地继续,直到子数组变为单个元素或空,此时排序完成。因此,粗体代码块本质上是检查左右子数组中是否还有未排序的元素,并递归地应用
quickSort
函数对这些子数组进行排序。这个递归过程最终是按照升序对整个数组进行排序。