算法学习——递归之快速排序
2023-02-18 16:36:59 时间
算法描述
快速排序
算法思路
-
快速排序算法的基本思路为从数组中选择一个数为基准数,之后,将比基准数小的数放在左边,比基准数大的数放在右边(分为了两个区),之后将左边(小于基准数)与右边(大于基准数)再次进行上述操作,一直重复直到无法再分为止
-
用户输入n,使用随机数产生n个数放入到数组a中
-
调用递归方法
sort()
PS:下面的数组a是全局变量
算法实现
System.out.println("输入数值个数n:");
Scanner scanner = new Scanner(System.in );
int n = scanner.nextInt();
scanner.close();
a = new int[n+1];
//随机赋值,留下a[0]存放基准数
for (int i = 1; i < n+1; i++) {
a[i]= (int) (Math.random()*100);
}
//输出数组a
for (int i = 1; i < n+1; i++) {
System.out.print(a[i]+" ");
}
sort(1,n);
//输出排序后的数值
System.out.println("");
for (int i = 1; i <n+1 ; i++) {
System.out.print(a[i]+" ");
}
}
public static void sort(int m1,int m2){
int i,j;
if(m1<m2){
i=m1;
j=m2;
a[0]=a[i];//每次的基准数都是传入分区的第一个数
//当i=j,即是完成了该分区的排序
while (i != j) {
//从右边开始扫描,直到不满足条件(也就是发现了一个数小于基准数,放入到左边的分区)
while(a[j]>=a[0] && j>i){
j--;
}
if(i<j){
a[i]=a[j];
i++;
}
//从左边开始扫描,直到不满足条件(也就是发现了一个数大于基准数,放入到右边的分区)
while(a[i]<=a[0] && j>i){
i++;
}
if(i<j){
a[j]=a[i];
j--;
}
}
a[i]=a[0];//将之前的基准数赋值给a[i]
//i已经存放了基准数,所以以i为分界线分为两个区,继续递归
sort(m1,i-1);
sort(i+1,m2);
}
return;
}
结果
相关文章
- 精讲响应式WebClient第6篇-请求失败自动重试机制,强烈建议你看一看
- 完美解决方案-雪花算法ID到前端之后精度丢失问题
- 精讲响应式WebClient第5篇-请求超时设置与异常处理
- 精讲响应式WebClient第4篇-文件上传与下载
- 精讲响应式WebClient第3篇-POST、DELETE、PUT方法使用
- 精讲响应式WebClient第2篇-GET请求阻塞与非阻塞调用方法详解
- 精讲响应式webclient第1篇-响应式非阻塞IO与基础用法
- 精讲RestTemplate第10篇-使用代理作为跳板发送请求
- 精讲RestTemplate第9篇-如何通过HTTP Basic Auth认证
- 精讲RestTemplate第8篇-请求失败自动重试机制
- 精讲RestTemplate第7篇-自定义请求失败异常处理
- 精讲RestTemplate第6篇-文件上传下载与大文件流式下载
- SpringBoot实现本地存储文件上传及提供HTTP访问服务
- 精讲RestTemplate第5篇-DELETE、PUT等请求方法使用详解
- 精讲RestTemplate第4篇-POST请求方法使用详解
- MinIO很强-让我放弃FastDFS拥抱MinIO的8个理由
- 在IntelliJ IDEA中多线程并发代码的调试方法
- 精讲RestTemplate第3篇-GET请求使用方法详解
- 超给力,一键生成数据库文档-数据库表结构逆向工程
- 精讲RestTemplate第2篇-多种底层HTTP客户端类库的切换