记录一下能用快排的题
先给出快排的版，默写一遍。。
void quick_sort(int q[],int l,int r)
{
if(l>=r) return;
int x=q[l],i=l-1,j=r+1;
while(i<j)
{
do {i++;} while(q[i]<x);
do {j--;} while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j);
qucik_sort(q,j+1,r);
}
1.第k小数
https://www.acwing.com/problem/content/788/
这道题把版改一点就行，判断两个分支进入哪个。。。
https://www.acwing.com/problem/content/submission/code_detail/124740/
这道题可以用快排的一次循环来进行，判断条件需要改变一下，将左边的数全部为奇数，右边数全部为偶数，再对应一次交换，也算一道很不错的简单题。
https://leetcode-cn.com/submissions/detail/20161423/
3.第k大数 转化为第k小数
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/comments/
堆排序
堆排序要写一个小根堆，然后进行维护。建堆O(N)，down(logn）
先默写下
int h[N],size;
void dn(int x)
{
int t=u;
if(u*2<=size&&h[u*2]<h[t]) t=u*2;
if(u*2+1<=size&&h[u*2+1]<h[t]) t=u*2+1;
if(u!=t)
{
swap(h[u],h[t]);
dn(t);
}
}
void make_heap(int n)
{
for(int i=n/2;i;i--)
dn(i);
}
void heap_sort(int n)
{
make_heap(n);
cout<<a[1]<<endl;
a[1]=a[size];
size--;
dn(1);
}
堆的其他操作
void up(int x)
{
while(x/2&&h[x]<h[x/2])
{
swap(h[x/2],h[x]);
up(x/2);
}
}
操作堆的几个必要步骤
1.插入一个数x
h[++size]=x up(size)
2.输出最小的数
h[1]
- 删除当前集合中的最小值
h[1]=h[size] size--; down(1);
大根堆的写法，抄了个
template<typename Tp>
class heap{ //heap是大根堆
private:
Tp arr[MAX_SIZE+10];
int size;
public:
heap()
{
memset(arr,0,sizeof(arr));
size=0;
}
heap(Tp *a,int sz)
{
for(int i=1;i<=sz;i++)
arr[i]=a[i];
size=sz;
}
bool empty()
{
return size?false:true;
}
void push(const Tp &val)
{
arr[++size]=val;
int i=size;
while(i/2&&arr[i/2]<arr[i])
{
swap(arr[i],arr[i/2]);
i/=2;
}
}
Tp top()
{
if(size==0) printf("NO TOP\n");
return arr[1];
}
void pop()
{
swap(arr[1],arr[size]);
size--;int i=1,maxk;
while(i<=size)
{
maxk=i;
if(i*2<=size&&arr[maxk]<arr[i*2]) maxk=2*i;
if(i*2+1<=size&&arr[maxk]<arr[i*2+1]) maxk=2*i+1;
if(maxk==i) break;
swap(arr[i],arr[maxk]);i=maxk;
}
}
void make_heap(Tp *a,const int &sz)
{
size=sz;
for(int i=1;i<=sz;i++)
push(a[i]);
}
void clear()
{
size=0;
}
};
heap<int> h;
做题的时候还是主要采用优先队列，大根堆priority_queue<int> heap;
小根堆 priority_queue<int, vector<int>, greater<int>> heap;
