heapsort.cpp

比较各种排序的算法间的运行效率 自己写的不太完善

void heapsort(int *array, int num, int &contrastNum, int &moveNum)
{
	int total, i;
	int t, temp;
	int flag;
	
	//构造堆-------------------------------------------------------------------- 
	do
	{
		flag = 0;

		if((num-1)%2)
		{
			i = (num-2)/2;
			contrastNum++;
			if(array[i]<array[num-1])
			{
				temp = array[num-1];
				array[num-1] = array[i];
				array[i] = temp;
				moveNum++;
				flag = 1;
			}
			total = num-1;
		}
		else
			total = num;

		for(;(i=(total-2)/2)>=0;total-=2)
		{
			t = array[i*2+1]>array[i*2+2]?(i*2+1):(i*2+2);
			contrastNum++;
			if(array[t]>array[i])
			{
				temp = array[i];
				array[i] = array[t];
				array[t] = temp;
				moveNum+=3;
				flag = 1;
			}
		}
		
	}
	while(flag);
	//构造堆完成----------------------------------------------------------------
	
	//利用堆进行排序，将符合堆条件的首元素与最后对调----------------------------
    //然后再从新构造堆，提供给下一次对调---------------------------------------- 
	for(total=num;total>3;)
	{
		temp = array[0];
		array[0] = array[total-1];
		array[total-1] = temp;
		moveNum+=3;
		total--;

		for(i=0;i<(total-2)/2;)
		{
			t = array[i*2+1]>array[i*2+2]?(i*2+1):(i*2+2);
			contrastNum++;
			if(array[t]>array[i])
			{
				temp = array[t];
				array[t] = array[i];
				array[i] = temp;
				moveNum+=3;
				i = t;
			}
			else 
				break;
		}
	
		if(i==(total-2)/2)
		{
		if(total%2)
		{
			t = array[i*2+1]>array[i*2+2]?(i*2+1):(i*2+2);
			contrastNum++;
			if(array[t]>array[i])
			{
				temp = array[t];
				array[t] = array[i];
				array[i] = temp;
				moveNum+=3;
			}
		}
		else if(array[2*i+1]>array[i])
		{
			temp = array[2*i+1];
			array[2*i+1] = array[i];
			array[i] = temp;
			moveNum+=3;
		}
		}
	
	}
	//大体上完成了排序,还有头三个未处理-----------------------------------------
	
    //对一些特殊的进行处理，两个的或是三个的------------------------------------ 
	if(total==3)
	{
		t = array[1]>array[2]?1:2;
		contrastNum++;
		if(array[t]>array[0])
		{
			temp = array[t];
			array[t] = array[0];
			array[0] = temp;
			moveNum+=3;
		}

		temp = array[2];
		array[2] = array[0];
		array[0] = temp;
		moveNum+=3;

		total--;
	}

	if(total==2&&array[0]>array[1])
	{
		temp = array[0];
		array[0] = array[1];
		array[1] = temp;
		moveNum+=3;
	}
	// 完全完成处理,包括特殊情况------------------------------------------------ 
   
	return;

}//堆排序法