記錄一下能用快排的題
先給出快排的版，默寫一遍。。

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小數(shù)
https://www.acwing.com/problem/content/788/
這道題把版改一點就行，判斷兩個分支進(jìn)入哪個。。。
https://www.acwing.com/problem/content/submission/code_detail/124740/

2. 按奇偶排序數(shù)組 II

這道題可以用快排的一次循環(huán)來進(jìn)行，判斷條件需要改變一下，將左邊的數(shù)全部為奇數(shù)，右邊數(shù)全部為偶數(shù)，再對應(yīng)一次交換，也算一道很不錯的簡單題。
https://leetcode-cn.com/submissions/detail/20161423/
3.第k大數(shù) 轉(zhuǎn)化為第k小數(shù)
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/comments/

堆排序
堆排序要寫一個小根堆，然后進(jìn)行維護。建堆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.插入一個數(shù)x
h[++size]=x up(size)
2.輸出最小的數(shù)
h[1]

3. 刪除當(dāng)前集合中的最小值
   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;

做題的時候還是主要采用優(yōu)先隊列，大根堆priority_queue<int> heap;
小根堆 priority_queue<int, vector<int>, greater<int>> heap;