排序笔记

jer2021 · 2020-12-27 16:35:58 · 个人记录

堆排序

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int a[1000000];
int heap[1000000] ,cnt;
int n;
/*下标 
                1
            2       3
        4     5 | 6      7
*/
int query(){//查询最大 
    if(!cnt)return -1;
    return heap[1]; 
}
void insert(int x){//插入
    cnt++;
    heap[cnt]=x;
    int k=cnt;
    while(k!=1 && heap[k] > heap[k/2])swap(heap[k] ,heap[k/2]) ,k=k/2;
}
void del(int x){//删除
    swap(heap[x] ,heap[cnt]);
    heap[cnt]=0;
    cnt--;
    int w=x;
    while(heap[w*2] > heap[w] || heap[w*2 + 1] > heap[w]){
        int aa;
        if(heap[w*2] > heap[w*2 + 1])aa=w*2;
        else aa=w*2 + 1;
        swap(heap[aa] ,heap[w]);
        w=aa;
    }
} 
int main()
{
    cin >> n;
    for(int i=1 ,w;i<=n;i++){
        cin >> w;
        insert(w);
    }
    for(int i=1;i<=n;i++){
        a[i]=query();
        del(1);
    }
    for(int i=n;i>=1;i--)cout << a[i] << ' ';

}

快速排序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;
long long n;
long long a[10000005];
void qsort(int l ,int r){
    if(l >= r)return ;
    int key=rand()%(r-l+1) + l;
    swap(a[key] ,a[l]);
    int p=l,q=r;
    while(p < q){
        while(a[p] <= a[q] && p<=q)q--;
        swap(a[q] ,a[p]);
        while(a[p] < a[q] && p<=q)p++;
        swap(a[q] ,a[p]);
    }
    qsort(l ,p-1);
    qsort(p+1 ,r);
}
int main()
{
    srand(time(0));
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    qsort(1 ,n);
    for(int i=1;i<=n;i++)cout << a[i] << ' ';
}

归并排序

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

int n ,a[100005];
void Mergesort(int l ,int r){
    if(l==r)return ;
    int mid=(l + r) / 2;
    Mergesort(l,mid);
    Mergesort(mid + 1 ,r);
    int p=l ,q=mid + 1, k=l;
    int tmp[100005]={0};
    while(p <= mid && q <= r){
        if(a[p] > a[q]){
            tmp[k]=a[p];
            p++;
        }
        else{
            tmp[k]=a[q];
            q++;
        }
        k++;
    }
    while(p <= mid)tmp[k++]=a[p] ,p++;
    while(q <= r)tmp[k++]=a[q] ,q++;
    for(int i=l;i<=r;i++)a[i]=tmp[i];
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i];
    Mergesort(1 ,n);
    for(int i=n;i>=1;i--)cout << a[i] << ' ';
}