Java代码:利用快速排序算法将读入的 n 个数从小到大排序后输出及解释
时间: 2023-07-06 20:43:41 浏览: 60
以下是Java实现的快速排序算法:
```java
public class QuickSort {
public static void main(String[] args) {
int[] nums = {3, 5, 2, 6, 1, 7, 4};
quickSort(nums, 0, nums.length - 1);
for (int num : nums) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(nums, left, right);
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
public static int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
}
}
int temp = nums[i];
nums[i] = nums[right];
nums[right] = temp;
return i;
}
}
```
快速排序算法是一种分治算法,其基本思想是选取一个枢轴元素,将数组分成两部分,左边的元素小于枢轴元素,右边的元素大于枢轴元素。然后递归地对左、右两部分进行排序。
在上述代码中,`quickSort` 方法用于递归排序左右两部分,`partition` 方法用于选取枢轴元素并将数组分成两部分。具体来说,`partition` 方法选取数组最后一个元素作为枢轴元素,然后使用双指针法将数组分成左右两部分,左边的元素小于枢轴元素,右边的元素大于枢轴元素。最后将枢轴元素交换到正确的位置,返回枢轴元素的索引,用于递归排序左右两部分。
在 `main` 方法中,我们使用一个数组 `{3, 5, 2, 6, 1, 7, 4}` 来测试快速排序算法。程序输出结果为 `1 2 3 4 5 6 7`,即将数组从小到大排序后的结果。