知名的网站建设公司排名,网站虚拟主机,wordpress设置上传,安徽建设工程监督和信用平台/懂了和写出来是两码事啊啊......orz./
Talk is cheap, show me the code
一、快速排序
直接背模板就能过#xff1a; 当xq[lr1]的边界情况 此时x取的是序列中间靠左的位置(如果序列个数为奇,则取正中间,如果为偶,则取中间靠左),此时如果元素个数为2, 则中间靠左就… /懂了和写出来是两码事啊啊......orz./
Talk is cheap, show me the code
一、快速排序
直接背模板就能过 当xq[lr1]的边界情况 此时x取的是序列中间靠左的位置(如果序列个数为奇,则取正中间,如果为偶,则取中间靠左),此时如果元素个数为2, 则中间靠左就是第1个元素,这时就跟xq[l]的边界情况一致了,所以这时只能用sort(l,j),sort(j1,r); AcWing 785. 快速排序 - AcWing #include iostream
#include cstring
#include algorithmusing namespace std;
const int N 1e5 10;
int q[N],n;
void quick_sort(int l,int r)
{if(lr) return; //数组中只有一个或数组为空int x q[lr1];int i l-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(l,j);quick_sort(j1,r);//此处是边界处理
}
int main()
{scanf(%d,n);for(int i0;in;i) scanf(%d,q[i]);quick_sort(0,n-1);for(int i 0;in;i) printf(%d ,q[i]);return 0;
} 扩展第K个数活动 - AcWing 多家了一步判断第k个数是在左边还是在右边 在左边区间长度j-l1k,开始l,结束j在区间中第k个数。 在右边区间长度j-l1k,开始j1,结束r在区间中第k -j-l1个数。 #include iostream
using namespace std;
const int N 1000010;
int q[N];//返回值是int
int quick_sort(int q[],int l,int r,int k)//要写int q[]
{if(lr) return q[l];int il-1,jr1,xq[(lr)1];while(ij){do i;while(q[i]x);do j--;while(q[j]x);if(ij) swap(q[i],q[j]);}if(j-l1k) return quick_sort(q,l,j,k);else return quick_sort(q,j1,r,k-(j-l1));//判断k与j的大小如果在左边就返回左边的数
}
int main()
{int n,k;scanf(%d%d, n, k);for (int i 0; i n; i ) scanf(%d,q[i]);cout quick_sort(q,0,n-1,k)endl;return 0;
}时间复杂度
最坏逆序的 二、归并排序
AcWing 787. 归并排序的证明与边界分析 - AcWing
时间复杂度O(nlogn)
#include iostream
#include cstring
#include algorithm
const int N 1e510;
int a[N],temp[N];
using namespace std;
void merge_sort(int q[],int l,int r)
{if(lr) return;int mid (lr)1;merge_sort(q,l,mid), merge_sort(q,mid1,r);//递归时mid1成为lint k 0,il,jmid1;while (imid jr){if(q[i]q[j]) temp[k]q[i];else temp[k] q[j];}while(imid) temp[k]q[i];while(jr) temp[k]q[j];for(int i l,j0;ir;i,j) q[i] temp[j];}
int main()
{int n;scanf(%d, n);for (int i 0; i n; i ) scanf(%d,a[i]);merge_sort(a,0,n-1);for (int i 0; i n; i ) printf(%d ,a[i]);return 0;
}
难一点的求逆序对 基本思路设置一个mid先求左半边内部和右半边内部的逆序对的数量直接求 两个数同时出现在左半边或同时出现在右半边 然后再用归并的思想左半边的指针i,右半边的指针j。此时左半边和右半边都是有序的从小到大如果ij是一对逆序对那么在左半边有mid-l1个关于j的逆序对。 AcWing 788. 逆序对的数量-要点 - AcWing #includeiostream
using namespace std;
const int N1e510;
int q[N], tmp[N];
int n;
typedef long long LL;LL merge_sort(int l, int r){if(lr) return 0;LL s0;int midlr1;smerge_sort(l, mid)merge_sort(mid1, r);int il, jmid1, k0;while(imid jr){if(q[i]q[j]) tmp[k]q[i];else {s mid-i1;tmp[k]q[j];}}while(imid) tmp[k]q[i];while(jr) tmp[k]q[j];for(int il, k0;ir;i, k) q[i]tmp[k];return s;
}int main(){cinn;for(int i0;in;i) scanf(%d, q[i]);coutmerge_sort(0, n-1) ;return 0;} 三、二分排序
整数二分
基本分治算法AcWing 789. 二分算法的证明和边界分析 - AcWing
#includeiostream
using namespace std;
const int N 100010;
int n,m;//m个查询
int q[N];int main()
{scanf(%d%d, n, m);for (int i 0; i n; i ) scanf(%d, q[i]);while (m -- ){int x;//输入要查询的数scanf(%d,x);int l0,rn-1;while(lr)//寻找右边分界点保证右边界点一直大于或等于x然后左边靠近else{int mid lr1;//向下取整if(q[mid]x) r mid;//向左边缩小else l mid1;//向右边缩小}if(q[l]!x) cout-1 -1endl;//不存在else{cout l ;//输出起始位置int l0,rn-1;while(lr)//寻找左边分界点,保证左边界点一直小于或等于x,然后右边靠近{int mid lr11;//mid向上取整if(q[mid]x) lmid;//else r mid-1;}cout l endl;}}return 0;
}
循环终止时 l r
易知 l不可能比 r 大 , 故 l r, 根据循环不变式l 就是答案点 res 另一种方法推荐使用不需要考虑mid1、mid-1的二分查找模板希望大家都能学会_一支彩色铅笔csdn_一支彩色铅笔的博客-CSDN博客 时间复杂度logn,因为指针每次移动都向边界移动 区域长度缩小一半。 细节点
