堆排序
include<iostream>
include<vector>
using namespace std;
class HeapSort{
private:
int len;
vector<int> list;
public:
/* 構(gòu)造函數(shù) */
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);//不斷調(diào)整為最大堆
}
}//end heap_sort()
/* 堆的建立或調(diào)整 */
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的 關(guān)鍵碼大則不做調(diào)整
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<<"請(qǐng)輸入要排序的數(shù)字個(gè)數(shù):"<<endl;
cin>>_len;
cout<<"請(qǐng)輸入要排序的數(shù)字:"<<endl;
for(int i=0; i<_len; i++){
cin>>digit;
_list.push_back(digit);
}
HeapSort* mazhe = new HeapSort(_list, _len);
mazhe->heap_sort();
cout<<"排序后的數(shù)為:"<<endl;
mazhe->out();
}
