堆排序

include<iostream>

include<vector>

using namespace std;

class HeapSort{

private:
    int len;
    vector<int> list;
public:
    /* 构造函数 */ 
    HeapSort(vector<int> _list, int _len){
        
        for(int i=0; i<_len; i++) list.push_back(_list[i]);
        len = _len;
        
    }//end HeapSort()
    
    /* 堆排序 */ 
    void heap_sort(){
        
        for(int i=(len-2)/2; i>=0; i--) filterDown(i, len-1);//建立堆
        
        for(int i=len-1; i>0; i--){
            
            swap(0, i);
            filterDown(0, i-1);//不断调整为最大堆 
        }           
        
    }//end heap_sort()
    
    /* 堆的建立或调整 */ 
    void filterDown(int current, int last){
        
        int child = current*2+1;//child为current子女的位置
        int temp  = list[current];
        
        while(child <= last){
            
            //让child指向子女最大的位置 
            if(child<last && list[child+1]>list[child]) child++;
            //temp的 关键码大则不做调整 
            if(temp >= list[child]) break;
            //否则子女中较大的上移
            else{
                
                list[current] = list[child];
                current = child;
                //current下降到子女位置 
                child   = 2*child+1;
            } 
            
        } 
        
        list[current] = temp; 
        
    }//end filerDown()
    
    /* 交换 */ 
    void swap(int i, int j){
        
        int temp = list[i];
        list[i]  = list[j];
        list[j]  = temp;
    } 
    
    /* 输出 */
    void out(){
        
        for(int i=0; i<len; i++){
            
            cout<<list[i]<<" ";
        }
    }//end out()        

};

int main(){

vector<int> _list;
int     _len;
int    digit; 

cout<<"请输入要排序的数字个数:"<<endl;
cin>>_len;
cout<<"请输入要排序的数字:"<<endl;

for(int i=0; i<_len; i++){

    cin>>digit;     
    _list.push_back(digit); 
} 

HeapSort* mazhe = new HeapSort(_list, _len);

mazhe->heap_sort();

cout<<"排序后的数为:"<<endl;

mazhe->out(); 

}