如安在java中运用分治法中的疾速排序处理排序问题【JAVA教程】,java,分治法,快速排序
作者:搜教程发布时间:2019-11-30分类:JAVA教程浏览:32评论:0
问题形貌:
输入一个数字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中运用分治法中的疾速排序处理排序问题的细致内容,更多请关注ki4网别的相干文章!
相关推荐
- java经典面试题集锦(五)_JAVA教程,java,面试题
- java中的换行符是什么_JAVA教程,java,换行符
- Java中变量必须先定义后使用么_JAVA教程,java,变量
- java中怎么定义接口_JAVA教程,java,接口
- java中静态代码块有什么特点_JAVA教程,java,静态代码块
- java中return语句有什么作用_JAVA教程,java,return
- Java对文件的读写操作(图文详解)_JAVA教程,java
- java经典面试题集锦(四)_JAVA教程,java,面试题
- 八种基本数据类型分别是什么?_JAVA教程,java,基本数据类型
- java如何将字符串转为数组_JAVA教程,java,字符串,数组
你 发表评论:
欢迎- JAVA教程排行
-
- 1接口中只能定义常量和抽象方法,对么_JAVA教程,接口,常量,抽象方法
- 2java中sleep的用法是什么?_JAVA教程,java,sleep
- 3Java中变量必须先定义后使用么_JAVA教程,java,变量
- 4java中的换行符是什么_JAVA教程,java,换行符
- 5Java如何获取字符在字符串中的位置_JAVA教程,Java,字符,字符串
- 6java经典面试题集锦(五)_JAVA教程,java,面试题
- 7java中静态代码块有什么特点_JAVA教程,java,静态代码块
- 8equals()函数与“==”的作用分别是什么_JAVA教程,equals(),==
- 9continue语句的作用是什么_JAVA教程,continue,作用
- 最新文章
- 广而告之