快速排序模板(cpp)
2022/8/11 6:25:49
本文主要是介绍快速排序模板(cpp),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速排序
一般情况下,快速排序的时间复杂度是\(O(n logn)\)
在最坏的情况下,快速排序的时间复杂度是\(O(n^2)\)
快速排序模板
void quick_sort(int q[],int l,int r){ if(l>=r)return; int i = l-1,j = r+1,mid = q[(l+r)/2]; while(i<j){ do i++;while(q[i]<mid); do j--;while(q[j]>mid); if(i<j)swap(q[i],q[j]); } quick_sort(q,l,j),quick(q,j+1,r); }
在这里,q是待排序的数组,l是左边界,r是右边界
引申算法
快速选择算法
int quick_choose(int q[],int l,int r,int k){ if(l>=r)return q[l]; int i = l-1,j = r+1,mid = q[(l+r)/2]; while(i<j){ do i++;while(q[i]<mid); do j--;while(q[j]>mid); if(i<j)swap(q[i],q[j]); } int sl = j-l+1; if(sl>=k)return quick_choose(q,l,j,k); else return quick_choose(q,j+1,r,k-sl); }
与快排的思路类似,可以快速找出数组q中l~r中第k大得数字。
更方便的方法
排序
c++中可以用库函数
sort(q,q+n)
寻找第k个数
nth_element(q,q+k-1,q+n);
注意这里的k是从1开始计的
这篇关于快速排序模板(cpp)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享