有没有可以做兼职的网站吗,今天的新闻 最新消息摘抄,重庆建设教育协会网站首页,江西省住房城乡建设部网站快速排序采用---分治策略
L |------x-------------| R
第一步确定分界点#xff1a;q[l],q[(lr)/2],q[r]随机
第二步调整范围#xff1a;L |--------x|x------------| R
第三步递归处理左右两端
两种做法#xff1a;
第一种#xff1a;暴力解决
另外定义两个…快速排序采用---分治策略
L |------x-------------| R
第一步确定分界点q[l],q[(lr)/2],q[r]随机
第二步调整范围L |--------x|x------------| R
第三步递归处理左右两端
两种做法
第一种暴力解决
另外定义两个数组a[],b[]
判断q中的数组元素与x进行比较小于x的放进a大于x的放进b
最后将ab放进数组q中可以实现左边的均小于x右面的均大于x。
时间复杂度为on可以考虑
优雅的做法
在头部和尾部分别定义两个指针两个指针同时往中间走
左面的指针先走当左面指针对应的数据小于x时继续往后走当左面指针对应的数据大于x时i就停下来则去移动j指针同理当j大于x时指针向左移动当j小于x时指针停止。
当两个指针都停止时进行swap交换那么交换完继续按照以上步骤执行直到i和j相遇那么左面的数据均小于x右面的数据均大于x。 边界问题背算法
#includeiostream
using namespace std;const int N1e610;
int n;
int q[N];void quick_sort(int q[],int l,int r){if(lr)return;int xq[(lr) / 2],il-1,jr1;while(ij){do i;while(q[i]x);do j--;while(q[j]x);if(ij){swap(q[i],q[j]);}}quick_sort(q,l,j);quick_sort(q,j1,r);}int main(){scanf(%d,n);for(int i0;in;i){scanf(%d,q[i]);}quick_sort(q,0,n-1);for(int i0;in;i){printf(%d,q[i]);}}
注意边界值要取中间值边界值容易死循环
