锐客网

  1. 首页 > it技术 > >

快排|快排,并归排序，堆排序 专题

记录一下能用快排的题
先给出快排的版，默写一遍。。

void quick_sort(int q[],int l,int r) { if(l>=r) return; int x=q[l],i=l-1,j=r+1; while(ix); if(i

1.第k小数
https://www.acwing.com/problem/content/788/
这道题把版改一点就行，判断两个分支进入哪个。。。
https://www.acwing.com/problem/content/submission/code_detail/124740/
  1. 按奇偶排序数组 II
这道题可以用快排的一次循环来进行，判断条件需要改变一下，将左边的数全部为奇数，右边数全部为偶数，再对应一次交换，也算一道很不错的简单题。
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]
【快排|快排,并归排序，堆排序 专题】堆的其他操作
void up(int x) { while(x/2&&h[x]

操作堆的几个必要步骤
1.插入一个数x
h[++size]=x up(size)
2.输出最小的数
h[1]
  1. 删除当前集合中的最小值
    h[1]=h[size] size--; down(1);
大根堆的写法，抄了个
template 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] h;

做题的时候还是主要采用优先队列，大根堆priority_queue heap;
小根堆 priority_queue, greater> heap;

    推荐阅读


    上一篇：《微信平民创业》

    下一篇：不在状态