利用快速排序算法将读入的 n 个数从小到大排序后输出。JAVA
时间: 2023-07-06 17:33:34 浏览: 45
好的,下面是利用快速排序算法将读入的 n 个数从小到大排序后输出的 JAVA 代码:
```java
import java.util.Scanner;
public class QuickSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
quickSort(nums, 0, n - 1);
for (int i = 0; i < n; i++) {
System.out.print(nums[i] + " ");
}
}
public static void quickSort(int[] nums, int left, int right) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
}
public static int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && nums[i] <= pivot) {
i++;
}
while (i <= j && nums[j] > pivot) {
j--;
}
if (i < j) {
swap(nums, i, j);
}
}
swap(nums, left, j);
return j;
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```
这段代码中,我们先读入 n 个数,然后利用快速排序算法将它们从小到大排序,最后输出排序后的结果。具体来说,我们定义了一个 quickSort 函数和一个 partition 函数,其中 quickSort 函数用来递归地对数组进行分区,而 partition 函数则用来对数组进行一次划分。在 partition 函数中,我们首先选取一个基准元素,然后利用两个指针 i 和 j 分别从数组的左右两端开始向中间扫描,直到它们相遇。在扫描时,如果 i 指向的元素小于等于基准元素,就向右移动 i 指针;如果 j 指向的元素大于基准元素,就向左移动 j 指针;如果 i 和 j 指向的元素都不符合要求,就交换它们。最后,我们将基准元素与 j 指向的元素交换位置,以保证基准元素左边的元素都比它小,右边的元素都比它大。