当前位置：首页 > news >正文

【已解决】键盘输入数字-使用JAVA语言实现键盘输入的数字再通过快速排序算法输出

news 2024/11/15 4:48:00

文章目录

一、前言
- 任务描述
- 相关知识
- - 分治策略：
  - 编程要求
  - 测试说明
二、具体代码实现
总结

一、前言

—快速排序

任务描述

在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在这两个子序列的中间，这个过程称作划分。
　　然后对两个子序列分别重复上述过程，直至每个子序列内只有一个记录或空为止。

本关任务：编写一个能使用快速排序的思想进行整数排序的小程序。

二、具体代码实现

import java.util.Scanner;public class QuickSort {public static void main(String[] args) {//键盘输入流的录入代码Scanner scanner = new Scanner(System.in);// 读取输入，返回值是一个整数型类型。int n = scanner.nextInt();int[] arr = new int[n];// 定义一个名字为arr的数组，数组里边的长度是n，也就是我们输入的数字。for (int i = 0; i < n; i++) {   // 对我们输入的数字大小的数组进行遍历，我们输入几就遍历循环几次。arr[i] = scanner.nextInt(); // 每循环一次就把输入的数字几放到数组的第几个位置，默认位置从1开始}// 显示排序前的数组System.out.print("排序前:");display(arr); // 定义的一个display的方法。// 快速排序quickSort(arr, 0, n - 1);// 显示排序后的数组System.out.print("排序后:");display(arr);scanner.close(); // scanner 键盘录入的操作很站系统资源所以需要调用close方法。}// 输出数组public static void display(int[] arr) {for (int num : arr) {    // 每输入一个就空一个System.out.print(num + " ");}System.out.println(); // 换行}// 划分算法，定义一个划分的方法，参数传需要对那个数组进行操作，最低位，和最高位。public static int partition(int[] arr, int low, int high) {int pivot = arr[low]; // 最低位的数组赋给基准变量pivot// 选择基准int left = low + 1; // 每次最低位加一依次往右移动int right = high; // 默认初始值是最高位在最右边的数rightwhile (left <= right) {  // 一个while循环判断最低位+1的数是否小于等于右边的数// 找到大于基准的左边元素，核心代码，比基准元素大的但是在右边     while (left <= high && arr[left] <= pivot) {left++;}// 找到小于基准的右边元素while (right >= low + 1 && arr[right] >= pivot) {right--;}// 交换if (left < right) {swap(arr, left, right);}}// 将基准元素放到正确的位置swap(arr, low, right);return right;// 返回基准的最终位置}// 交换数组元素，交换位置。public static void swap(int[] arr, int i, int j) {int temp = arr[i]; //定义的一个中间变量用来交换arr[i] = arr[j]; arr[j] = temp;}// 快速排序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);// 对右子序列进行排序}}
}