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

devtools/2024/9/24 1:57:57/

文章目录

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


一、前言

—快速排序

任务描述

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

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

相关知识

如何求解?假设a[s] a[s+1] … … … a[t]待排序的元素。

在这里插入图片描述

分治策略:

  1. 分解:将原序列a[s…t]分解成两个子序列a[s…i-1]和a[i+1…t],其中i为划分的基准位置。
  2. 求解子问题:若子序列的长度为0或为1,则它是有序的,直接返回;否则递归地求解各个子问题。
  3. 合并:由于整个序列存放在数组中a中,排序过程是就地进行的,合并步骤不需要执行任何操作。

在这里插入图片描述

编程要求

根据提示,在右侧编辑器补充代码,实现快速排序。

测试说明

编辑器对你编写的代码进行测试:

测试输入:10,2,5,1,7,10,6,9,4,3,8;
预期输出:
排序前:2 5 1 7 10 6 9 4 3 8
排序后:1 2 3 4 5 6 7 8 9 10

测试输入:5,1,151,12,22,100;

预期输出:
排序前:1 151 12 22 100
排序后:1 12 22 100 151

二、具体代码实现

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[] 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);// 对右子序列进行排序}}
}

总结

  1. 选择一个基准值(pivot),通常可以选择数组的第一个元素、最后一个元素或者中间元素。
  2. 对数组进行划分,将小于基准值的元素放在基准值左边,大于基准值的元素放在基准值右边。
  3. 分别对左右两个子数组重复上述步骤,直到子数组的长度为 1 或 0。

http://www.ppmy.cn/devtools/116264.html

相关文章

spring怎么识别拦截器 异常处理器

Spring框架中识别和调用拦截器&#xff08;Interceptor&#xff09;和异常处理器&#xff08;HandlerExceptionResolver&#xff09;是通过容器内部的组件扫描和自动装配机制来完成的。 拦截器&#xff08;Interceptor&#xff09;: Spring MVC 的拦截器必须实现 HandlerInte…

Spring Boot-应用启动问题

在使用 Spring Boot 进行开发时&#xff0c;应用启动问题是开发人员经常遇到的挑战之一。通过有效排查和解决这些问题&#xff0c;可以提高应用的稳定性和可靠性。 1. Spring Boot 启动问题的常见表现 Spring Boot 应用启动失败通常表现为以下几种情况&#xff1a; 应用启动…

QT----基于QML的计时器

赶上了实习的末班车,现在在做QML开发,第一天的学习成果,一个计时器.逻辑挺简单的,纯QML实现,代码在仓库QT-Timer 多线程优化 在使用的过程中发现自己的计时器时间会慢,并且一直点击记录的话时间1s可以走10s,排查发现是在计时器的间隔取得太小了,取了1太过于消耗资源,改成10的…

【QT基础】创建项目项目代码解释

目录 前言一&#xff0c;使⽤Qt Creator 新建项目1. 新建项目2. 选择项⽬模板3. 选择项⽬路径4. 选择构建系统5. 填写类信息设置界⾯6. 选择语⾔和翻译⽂件7. 选择Qt套件8. 选择版本控制系统9. 最终效果 二&#xff0c;项目代码说明1. main.cpp文件2. Widget.h文件3. Widget.cp…

大数据系统调优:从DAG到单机

目标&#xff1a;优化T10的时效性全局DAG调度层优化&#xff1a;提前任务开始时间&#xff1a; 1. 优化慢结点&#xff1a;T10依赖了T4,T7,T8, 其中T8为瓶颈&#xff0c;如果T8能提前点完成&#xff0c;T10可以早点开始&#xff0c;就能早点完成 2. 快结点做更多预计算…

数据库_解决SQL Server数据库log日志过大,清理日志文件方法

SQL Server数据库日志文件过大的原因主要有几个方面&#xff1a; 事务日志记录了所有对数据库进行修改的操作&#xff0c;如插入、更新和删除&#xff0c;这些操作会不断增加日志文件的大小。 长时间运行且未正确结束的事务会持续占用事务日志中的空间&#xff0c;导致日志文…

Kubernets基础-包管理工具Helm详解

文章目录 什么是Helm?Helm 的基本概念Helm 的工作原理Helm 的主要功能使用 Helm 的步骤 values.yaml和Chart.yamlvalues.yaml 文件示例Chart.yaml 文件示例 什么是Helm? Helm 是 Kubernetes 的一个非常流行的包管理工具&#xff0c;它使得在 Kubernetes 上部署应用程序变得更…

医学数据分析实训 项目三 关联规则分析预备项目---购物车分析

文章目录 1 预备项目关联规则分析实践———购物车分析1 产生频繁集2 产生关联规则 1 预备项目 关联规则分析实践———购物车分析 import warnings import numpy as np import pandas as pd from mlxtend.frequent_patterns import apriori from mlxtend.frequent_patterns …