如何在java中使用分治法中的快速排序解决排序问题
问题描述:
输入一个数字N后,输入N个数字,将N个数字排序后输出。
输入:
输出:
算法设计:
快速排序的基本思想是基于分治策略的,其算法思想如下:
(1)分解:先从数列中取出一个元素作为基准元素.以基准元素为标准,将问题分解为两个子序列,使小于或等于基准元素的子序列在左侧,使大于基准元素的子序列在右侧.
(2)治理:对两个子序列进行快速排序.
(3)合并:将排好序的两个子序列合并在一起,得到原问题的解.
免费视频教程推荐:java学习视频
设当前待排列的序列为R[low:high],其中low≤high,如果序列的规模足够小,则直接进行排序,否则分3步处理:
(1)分解:在R[low:high]中选定一个元素R[pivot],以此为标注将要排序的序列划分为两个序列R[low:pivot-1]和R[pivot+1:high],并使序列R[low:pivot]中所有元素的值小于等于R[pivot],序列R[pivot+1:high]中所有的元素均大于R[pivot],此时基准元素已经位于正确的位置,它无需参加后面的排序.
(2)治理:对于两个子序列R[low:pivot-1]和R[pivot+1:high],分别通过递归调用快速排序算法来进行排序.
(3)合并:由于对R[low:pivot-1]和R[pivot:high]的排序是原地进行的,所以在R[low:pivot-1]和R[pivot+1:high]都已经排好序后,合并步骤无需做什么,序列R[low:high]就已经排好序了.
示例代码:
//程序目的:用分治法中的快速排序解决排序问题 import java.util.Scanner; public class text2 { public static void swap(int array[],int a,int b){//交换函数 int temp; temp=array[a]; array[a]=array[b]; array[b]=temp; } public static int Partition(int r[],int low,int high){ int i=low ; int j=high; int pivot=r[low];//基准元素 while(i<j) { while (i < j && r[j] > pivot) //向左扫描 j--; if (i < j) { swap(r, i++, j); } while (i < j && r[i] <= pivot) {//向右扫描 i++; } if (i < j) { swap(r, i, j--); } } return i; } public static void QuickSort(int R[],int low,int high){//快速排序递归算法 int mid; if(low<high){ mid=Partition(R,low,high);//基准位置 QuickSort(R,low,mid-1);//左区间递归快速排序 QuickSort(R,mid+1,high);//右区间递归快速排序 } } public static void main(String args[]){ Scanner sc=new Scanner (System.in); int i; int n;//数据的个数 System.out.println("请先输入要排序元素的个数"); n=sc.nextInt(); System.out.println("请输入要排序的数据"); int []a=new int[n]; for (i=0;i<n;i++){ a[i]=sc.nextInt(); } QuickSort(a,0,n-1); System.out.println("排序后的数据"); for (i=0;i<n;i++){ System.out.print(a[i]+" "); } System.out.println(); } }
运行结果:
相关学习教程推荐:java入门教程
以上是如何在java中使用分治法中的快速排序解决排序问题的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

Java 8引入了Stream API,提供了一种强大且表达力丰富的处理数据集合的方式。然而,使用Stream时,一个常见问题是:如何从forEach操作中中断或返回? 传统循环允许提前中断或返回,但Stream的forEach方法并不直接支持这种方式。本文将解释原因,并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读: Java Stream API改进 理解Stream forEach forEach方法是一个终端操作,它对Stream中的每个元素执行一个操作。它的设计意图是处

PHP是一种广泛应用于服务器端的脚本语言,特别适合web开发。1.PHP可以嵌入HTML,处理HTTP请求和响应,支持多种数据库。2.PHP用于生成动态网页内容,处理表单数据,访问数据库等,具有强大的社区支持和开源资源。3.PHP是解释型语言,执行过程包括词法分析、语法分析、编译和执行。4.PHP可以与MySQL结合用于用户注册系统等高级应用。5.调试PHP时,可使用error_reporting()和var_dump()等函数。6.优化PHP代码可通过缓存机制、优化数据库查询和使用内置函数。7

PHP和Python各有优势,选择应基于项目需求。1.PHP适合web开发,语法简单,执行效率高。2.Python适用于数据科学和机器学习,语法简洁,库丰富。

胶囊是一种三维几何图形,由一个圆柱体和两端各一个半球体组成。胶囊的体积可以通过将圆柱体的体积和两端半球体的体积相加来计算。本教程将讨论如何使用不同的方法在Java中计算给定胶囊的体积。 胶囊体积公式 胶囊体积的公式如下: 胶囊体积 = 圆柱体体积 两个半球体体积 其中, r: 半球体的半径。 h: 圆柱体的高度(不包括半球体)。 例子 1 输入 半径 = 5 单位 高度 = 10 单位 输出 体积 = 1570.8 立方单位 解释 使用公式计算体积: 体积 = π × r2 × h (4

PHP和Python各有优势,适合不同场景。1.PHP适用于web开发,提供内置web服务器和丰富函数库。2.Python适合数据科学和机器学习,语法简洁且有强大标准库。选择时应根据项目需求决定。

PHP适合web开发,特别是在快速开发和处理动态内容方面表现出色,但不擅长数据科学和企业级应用。与Python相比,PHP在web开发中更具优势,但在数据科学领域不如Python;与Java相比,PHP在企业级应用中表现较差,但在web开发中更灵活;与JavaScript相比,PHP在后端开发中更简洁,但在前端开发中不如JavaScript。
