6 堆排序

/*6 堆排序 *HEAP-SORT */#include<cstdlib>#include<iostream>#include<vector>#include<iomanip>using namespace std;typedef vector<int>::iterator ivecIte;#define parent(i) (0==(i%2) ? i/2 : (i-1)/2)#define left(i) 2*i#define right(i) 2*i+1size_t chkivIte(ivecIte iteB, ivecIte iteE){if(iteB > iteE) {cout<<"wrong in iterator range!"<<endl;exit(0);}return iteE - iteB;}void maxHeapify(vector<int> &ivec, ivecIte iteB, ivecIte iteE, ivecIte iteChk){size_t heapSize = chkivIte(iteB, iteE);//将迭代器转换成堆的下标size_t i = iteChk - iteB + 1;ivecIte largeIte = iteChk;//必要的初始化 /*条件传送指令要小心使用 *条件传送会提前运算两种结果后再判断 *必须先判断后使用条件传送指令 */if(left(i)<=heapSize) {ivecIte leftIte = iteB+left(i)-1;largeIte = (*leftIte>*iteChk) ? leftIte : iteChk;}if(right(i)<=heapSize) {ivecIte rightIte = iteB+right(i)-1;largeIte =(*rightIte>*largeIte) ? rightIte : largeIte;}if(iteChk != largeIte) {*iteChk = (*iteChk) ^ (*largeIte);*largeIte = (*iteChk) ^ (*largeIte);*iteChk = (*iteChk) ^ (*largeIte);maxHeapify(ivec, iteB, iteE, largeIte);}}void buildMaxHeap(vector<int> &ivec, ivecIte iteB, ivecIte iteE){size_t heapSize = chkivIte(iteB, iteE);size_t  indx = heapSize/2;ivecIte iteChk;for(size_t t = indx; 0 != t; --t) {iteChk = iteB + t - 1; maxHeapify(ivec, iteB, iteE, iteChk);}}void heapSort(vector<int> &ivec, ivecIte iteB, ivecIte iteE) {size_t heapSize = chkivIte(iteB, iteE);buildMaxHeap(ivec, iteB, iteE);ivecIte iteT;for(size_t t = heapSize; 1 != t; --t) {iteT =iteB + t - 1;//iteT肯定大于iteB,所以可以用^位操作符交换*iteT = (*iteB) ^ (*iteT);*iteB = (*iteB) ^ (*iteT);*iteT = (*iteB) ^ (*iteT);maxHeapify(ivec, iteB, iteT, iteB);}}int main(){vector<int> ivec;cout<<"input some integers with end-of-file!"<<endl;int inData;while(cin>>inData)ivec.push_back(inData);heapSort(ivec, ivec.begin(), ivec.end());for(ivecIte ite = ivec.begin(); ivec.end() != ite; ++ite)cout<<setw(5)<<*ite;cout<<endl;system("PAUSE");return EXIT_SUCCESS;}