排序笔记
jer2021
2020-12-27 16:35:58
### 堆排序
```cpp
#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] << ' ';
}
```
### 快速排序
```cpp
#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] << ' ';
}
```
### 归并排序
```cpp
#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] << ' ';
}
```