• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C++堆排序代码示范

OC/C/C++ 水墨上仙 1196次浏览

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;
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C++堆排序代码示范
喜欢 (0)
加载中……