C++堆排序代码示范

C++堆排序代码演示

/*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+1
size_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 = (*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;
}