堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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] << ' ';
	
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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] << ' ';
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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] << ' ';
}