算法之快速排序
2021/10/22 20:12:52
本文主要是介绍算法之快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速排序算法是分治法的一种
什么是分治法
(11条消息) 分治法的特征和步骤_我还能再写一年的博客-CSDN博客
快速排序的解法步骤
给定十个数字,2,5,1,7,10,6,9,4,3,8进行排序
第一次
一般来说,是以第一个数为基准,
2 | 5 | 1 | 7 | 10 | 6 | 9 | 4 | 3 | 8 |
->
1 |
2 |
5 | 7 | 10 | 6 | 9 | 4 | 3 | 8 |
以2为基准,分为两个,一个是比2小的,一个是比2大的,比2小的放在左边,比2大的放在右边
第二次
再将分下来的两个继续进行刚才的操作
1 |
->不需要再进行分解了
5 | 7 | 10 | 6 | 9 | 4 | 3 | 8 |
->以5为基准,将比5小的放在左边,将比5大的放在右边
4 | 3 |
5 |
7 | 10 | 6 | 9 | 8 |
第三次
左边部分
4 | 3 |
以4为基准,比4小的放在左边,比4大的放在右边
3 |
4 |
右边部分:
7 | 10 | 6 | 9 | 8 |
以7为基准,比7小的在左边,比7大的在右边
6 |
7 |
10 | 9 | 8 |
第四次
左边部分,不需要再进行上述步骤
右边部分:
10 | 9 | 8 |
以10为基准,比10小的放左边,比10大的放右边
9 | 8 |
10 |
第5次
左边部分:
9 | 8 |
以9为基准,比9小的放在左边,比9大的放在右边
8 |
9 |
右边部分:
不需要执行了
第6次
8 |
不需要执行了
代码执行:
分解
public static void Qu(int a[] , int s, int t){ if(s<t) { int i=Hua(a,s,t); Qu(a,s,i-1); Qu(a,i+1,t); } }
排序
public static int Hua(int a[] , int s, int t) { /** * s为0,也就是第一个值的数组下标 * t为a.length-1,为数组的个数-1 */ int i=s,j=t; int tmp=a[s];//基准 while(i!=j) { while(j>i&&a[j]>=tmp) j--; a[i]=a[j]; while(i<j&&a[i]<=tmp) { i++; a[j]=a[i]; } } a[i]=tmp; return i; }
完整代码
public static void disp(int a[],int n) { for(int i=0;i<=n;i++) { System.out.print(a[i]+"\t"); } System.out.print("\n"); } public static int Hua(int a[] , int s, int t) { /** * s为0,也就是第一个值的数组下标 * t为a.length-1,为数组的个数-1 */ int i=s,j=t; int tmp=a[s];//基准 while(i!=j) { while(j>i&&a[j]>=tmp) j--; a[i]=a[j]; while(i<j&&a[i]<=tmp) { i++; a[j]=a[i]; } } a[i]=tmp; return i; } public static void Qu(int a[] , int s, int t){ if(s<t) { int i=Hua(a,s,t); Qu(a,s,i-1); Qu(a,i+1,t); } } public static void main(String[] args) { //快速排序 /*Scanner s= new Scanner(System.in); int n; n=s.nextInt(); int [] arr =new int [n]; for(int i=0;i<=n-1;i++) { arr[i]=s.nextInt(); }*/ int n=10; int [] arr ={2,5,1,7,10,6,9,4,3,8}; disp(arr,n-1); Qu(arr,0,n-1); disp(arr,n-1); }
这篇关于算法之快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)