Closer's Space

梦河之上, 一叶扁舟

堆排序


堆排序

  • $O(n)$建大根堆
  • 大根堆的根即为当前堆的最大值结点, 交换到数组后面适当位置$O(1)$
  • 维护大根堆 $O(logn)$
  • 总复杂度:$O(nlogn)$
#include <bits/stdc++.h>
using namespace std;
int debug = 0;
#define Debug cout << "Debug: " << ++debug << endl;
int elem[110];
int N;
int heapSize;

void read(){
        cin >> N;
        for(int i = 1; i <= N; ++i)
                cin >> elem[i];
}
void outTree(int x, int depth){
        if(x > N) return;
        for(int i = 0; i < depth; ++i)
                cout << ' ';
        cout << elem[x] << endl;
        outTree(x << 1, depth + 1);
        outTree(x << 1 | 1, depth + 1);
}

void maxHeapfiy(int x){
        int l = x << 1;
        int r = x << 1 | 1;
        int large = x;
        if(r <= heapSize && elem[r] > elem[large]) large = r;
        if(l <= heapSize && elem[l] > elem[large]) large = l;
        if(large != x){
                swap(elem[x], elem[large]);
                maxHeapfiy(large);
        }
//      Debug;
//      outTree(1, 0);
}

void buildMaxHeap(){
        for(int i = N >> 1; i >= 1; --i)
                maxHeapfiy(i);
}

void heapSort(){
        heapSize = N;
        buildMaxHeap();
        for(int i = N; i >= 2; --i){
                swap(elem[1], elem[i]);
                --heapSize;
                maxHeapfiy(1);
        }
}

void output(){
        for(int i = 1; i <= N; ++i)
                cout << elem[i] << ' ';
        cout << endl;
}

int main(){
        freopen("in.txt", "r", stdin);
        read();
        heapSort();
        output();
        return 0;
}

博文最后更新时间:


评论

  • 暂无评论

发表评论

来访统计

访问量:107

评论总数:0