学步园

       最近关注一下数据算法面试的时候常考的题目，复习一下常用排序。以下是堆排序，常用在topK问题求解中。

// Heap sort;
void MaxHeapify(int * src, int pos,int count)
{
	int l = (pos<<1)+1;
	int r = l+1;
	int maxpos = pos;
	if (l<count && src[l]>src[pos])
	{
		maxpos = l;
	}
	if (r<count && src[r]>src[maxpos])
	{
		maxpos = r;
	}
	if (maxpos != pos)
	{
		int temp = src[maxpos];
		src[maxpos] = src[pos];
		src[pos] = temp;
		MaxHeapify(src,maxpos,count);
	}
}

void CreateMaxHeap(int * src,int count)
{
	for (int t = count>>1;t>=0;--t)
	{
		MaxHeapify(src,t,count);
	}
	return;
}

void HeapSort(int * src,int count)
{
	CreateMaxHeap(src,count);
	while (count--)
	{
		int t = src[0];
		src[0] = src[count];
		src[count] = t;
		MaxHeapify(src,0,count);	
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	int intarray[1024] = {0};
	for(int i = 0; i< 1024; ++i)
	{
		intarray[i] = i;
	}
	HeapSort(intarray,1024);
	return 0;
}