
问题描述:
输入一个数字n后,输入n个数字,将n个数字排序后输出。
输入:

输出:

算法设计:
快速排序的基本思想是基于分治策略的,其算法思想如下:
(1)分解:先从数列中取出一个元素作为基准元素.以基准元素为标准,将问题分解为两个子序列,使小于或等于基准元素的子序列在左侧,使大于基准元素的子序列在右侧.
(2)治理:对两个子序列进行快速排序.
(3)合并:将排好序的两个子序列合并在一起,得到原问题的解.
免费视频教程推荐:java学习视频
使用Atmosphere构建通过WebSocket、SSE、gRPC、WebTransport、MCP、A2A和AG-UI流传输的JVM代理网关,并带有治理钩子。
设当前待排列的序列为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> pivot) //向左扫描
j--;
if (i <p>运行结果:<br></p>
<p><img src="https://img.php.cn/upload/image/695/233/269/1574926626977367.png?x-oss-process=image/resize,p_40" title="1574926626977367.png" alt="3e404f4418a907d544ca47b1369eaf5.png"></p>
<p>相关学习教程推荐:<a href="https://www.php.cn/java/guide/" target="_blank">java入门教程</a></p></j>
Java免费学习笔记:立即使用
解锁 Java 大师之旅:从入门到精通的终极指南










