快速排序算法
2021/9/19 17:05:08
本文主要是介绍快速排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速排序:找到一个基数,然后把全部元素和基数进行比较,小于基数的放在左边,大于的放在右边,然后基数和左边最后一个数进行对调,基数所在位置就是最后正确的目标位置,同理后面的元素比较,一般我们以第一个元素设为基数
//a是待排序数组,p为左边界,r为右边界,递归调用 public static void QKSort(int[] a, int p, int r){ if(p<r){ //进行比较并交换基数和左边最后一个比基数小的数 int k = Compare(a,p,r); //返回调换后的基数位置 //基数位置已确定,对基数左右未确定的序列确定下一个新的基数的位置 QKSork(a,p,k-1); QKSork(a,k+1,r); } } //比较,得到基数位置 public static void Compare(int[] a, int p, int r){ //一般以第一个数为基数 int x = a[p]; //设置左右游标 int i = p; //左,后面++i排除了基数的影响 int j = r+1; //右,后面--j排除了越界的影响 while(true){ while(a[++i]<x && i<r);//从左边开始遍历,当左边出现比x大或越界的时候停下 while(a[--j]>x); //从最右边开始遍历,单右边出现比x小的时候停下 //当出现i>=j的时候,基数的正确位置已出现,已完成左小右大,跳出循环 if(i>=j){ break; } //未出现i>=j时,需要调换ij数据位置,保证左小右大,自己写一个交换函数,或者直接交换 Swap(a,i,j); } //跳出循环后,交换基数和左边最后一个比x小的数的位置,并返回基数现有位置 a[p] = a[j]; a[j] = x; return j; }
为了让时间复杂度出现最坏的几率变小,可以采用随机化的方式,只需要在上面基础上再添加一个函数即可。
//在序列范围内随机抽出一个数作为基数,和左边界的数进行对调 public static int random(int[] a, int p, int r){ //在p r范围内随机选中一个下标 int index = (int)(p+Math.random()*(r-p)); //对调基数和首元素位置,是为了方便调用上面的Compare()函数 Swap(a,p,index); return Compare(a,p,r); } //上面第一个函数 int k = Compare(a,p,r); //改为 int k = random(a,p,r);
这篇关于快速排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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题)