快排、归并排序
程序员文章站
2022-06-04 18:15:49
...
Powered by:AB_IN 局外人
5.18 直播总结。
一、快排模版
~~
void quick_sort(int a[],int l ,int r)
{
int i=l,j=r;
int mid=(l+r)>>1;//以中间为基准点,不断靠近基准点
int x=a[mid];
while(i<=j){
while(a[i]<x) i++;//注意这里是x,不是a[mid],因为a[mid]在另一个递归会变
while(a[j]>x) j--;
if(i<=j){
swap(a[i],a[j]);//基准数左边比他大的与右边比他小的数交换
i++;j--;
}
}
if(l<j) quick_sort(a,l,j);//再确立一个区间,一个基准数
if(l<r) quick_sort(a,i,r);
}
二、归并模版
~~
void _merge(int l,int mid,int r)
{
int p1=l,p2=mid+1;
for(int i=l;i<=r;i++){
if((p1<=mid) && ((p2>r) || a[p1] <= a[p2])){
b[i]=a[p1];
p1++;
}
else{
b[i]=a[p2];
p2++;
}
}
for(i=l;i<=r;i++) a[i]=b[i];
}
void erfen(int l,int r)
{
int mid=(l+r)/2;
if(l<r){
erfen(l,mid);
erfen(mid+1,r);
}
_merge(l,mid,r);
}
都是a为原数组。
三、deque
deque<int> dq
push_front () :
在deque容器的开始位置插入一个新的元素,位于当前的第一个元素之前。
push_back():
在当前的最后一个元素之后 ,在deque容器的末尾添加一个新元素。
pop_front():
删除deque容器中的第一个元素.
pop_back():
删除deque容器中的最后一个元素.
四、二叉树
完全二叉树,最后一层可以少连着的几个,但不能分开。
bitset还不会。等自学。
图片来自清楚姐姐的PPT。
完结。