永济市网站建设,2345网址导航官网官方电脑版,中国兰州网招聘,大连建设工程信息网官网官网官作者#xff1a;指针不指南吗 专栏#xff1a;算法篇 #x1f43e;或许会很慢#xff0c;但是不可以停下#x1f43e; 文章目录一、快速排序 ( Quick Sort )二、归并排序 ( Merge Sort )总结一、快速排序 ( Quick Sort )
1.思路 找出一个分界点#xff0c;随机的调整区间… 作者指针不指南吗 专栏算法篇 或许会很慢但是不可以停下 文章目录一、快速排序 ( Quick Sort )二、归并排序 ( Merge Sort )总结一、快速排序 ( Quick Sort )
1.思路 找出一个分界点随机的调整区间 分治双指针指向两边往中间走遇到不满足条件的停下直到两者都遇到不满足条件的交换位置直到两个指针相遇递归处理两段 分治 三步曲分成子问题解决子问题子问题合并成大问题 代码模板
void quick_sort (int q [ ] , int l , int r )
{if (l r) return ; //区间个数为 1或者 0返回int i l-1;jr1;xq[lr1]; // i指左边, j指最右边,范围大点要包含 l , r while(ij){do i;while(q[i]x); //指针移动直到出现不满足条件的情况do j--;while(q[j]x);if(ij) swap(q[i],q[j]; //找到 2个交换}quick_sort(q,l,j),quick_sort(q,j1,r); //递归}二、归并排序 ( Merge Sort )
1.思路 确定一个分界点递归排序合二为一 分成两组数据然后两组数据从最小的比较谁小放在temp数组其中一组数据已经走完了另一组还剩着把剩余的放在temp数组后面最后temp 赋值给 q 即原始数组 2.代码模板
void merge_sort(int q[],int l,int r)
{if(lr) return ; //区间只有一个元素或没有返回 int midlr1; //确定中间值 merge_sort(q,l,mid),merge_sort(q,mid1,r); //递归排序 int il,jmid1,k0;while(imidjr){if(q[i]q[j]) temp[k]q[i]; //谁小谁就先存储在temp中 else temp[k]q[j];}while(imid) temp[k]q[i]; //谁有剩余即其数大存储在temp后面 while(jr) temp[k]q[j];for(int il,j0;ir;i,j) q[i]temp[j]; //拷贝到原数组
}总结
快排和归并排序
思路上 快排是先处理两边再递归 归并是先递归在处理两边 时间复杂度上 快排 和 归并排序 的时间复杂度都是 O(log2nlog_{2}nlog2n ) 快排平均 O(log2nlog_{2}nlog2n )最坏情况可以达到 O(n2n^2n2)归并排序的最坏和最好情况都是 O(log2nlog_{2}nlog2n )
