#includeusing namespace std;#define left(i) (i * 2)#define right(i) (i * 2 + 1)int n, num[100 + 2]; void swap(int &a, int &b) { int c = a; a = b, b = c; } void Max_heap(int num[], int i, int m) { int l = left(i), r = right(i), largest = i; if(l <= m && num[largest] < num[l]) largest = l; if(r <= m && num[largest] < num[r]) largest = r; if(largest != i) { swap(num[largest], num[i]); Max_heap(num, largest, m); } } int main() { cin >> n ; for(int i = 1; i <= n; i++) cin >> num[i]; for(int i = n / 2; i >= 1; i--) Max_heap(num, i, n); for(int i = n; i >= 2; i--) { swap(num[1], num[i]); Max_heap(num, 1, i - 1); } for(int i = 1; i <= n; i++) cout << num[i] << " "; cout << endl; return 0; } //时间复杂度:O(nlgn)
通过维护一个大根堆/小根堆来实现数组元素的排序,优点是维护步骤容易理解,其涉及的一些细节操作会对线段树的书写多少有写辅助。
此代码的缺陷:swap函数并不用手写,节点编号用i << 1、i << 1 | 1 来计算可多少加快一点运算速度。