谁知道这是什么排序方式
  • 板块学术版
  • 楼主sjzwer_
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/21 21:40
  • 上次更新2024/11/22 09:00:59
查看原帖
谁知道这是什么排序方式
1097868
sjzwer_楼主2024/11/21 21:40

这是什么排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n , a[N];
void swapy(int x , int y){
	int tmp = a[x];
	a[x] = a[y];
	a[y] = tmp;
} 

void maxheap(int st , int en){
	int ro = st;
	int l = ro * 2;
	int r = l + 1;
	int maxidx = l;
	while(l <= en){
		if(r <= en && a[maxidx] < a[r]) maxidx = r;
		if(a[maxidx] > a[ro]){
			swapy(maxidx , ro);
			ro = maxidx;
			l = ro * 2;
			r = l + 1;
			maxidx = l;
		}else break;
	} 
}

void heapsort(){
	for(int i = n / 2 ; i >= 1 ; i--) maxheap(i , n);
	int lastt = n;
	for(int i = 1 ; i < n ; i++){
		swapy(1 , lastt);
		lastt--;
		maxheap(1 , lastt);
	}
}

int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	heapsort();
	for(int i = 1 ; i <= n ; i++) cout << a[i] << " "; 
	return 0;
}
2024/11/21 21:40
加载中...