算法 排序 堆排序

根据自己命名习惯与方便理解进行实现快速排序，仅做记录，后续完善。

void maxHeapify(vector& nums, int index, int heapSize)
{
	int left = index*2+1;
	int right = index*2+2;
	int maxIndex = index;

	if( left < heapSize && nums[maxIndex] < nums[left] )
		maxIndex = left; 
	if( right < heapSize && nums[maxIndex] < nums[right] )
		maxIndex = right;
	if(maxIndex != index)
	{
		swap(nums[index], nums[maxIndex]);
		maxHeapify(nums, maxIndex, heapSize);
	}
}              

void buildMaxHeapify(vector& nums, int heapSize)
{
	//从下而上构造最大堆
	for(int i=heapSize/2; i>=0 ; i--)
	{
		maxHeapify(nums, i, heapSize);  
	}
}

void heapSort(vector& nums)
{
	int heapSize = nums.size();
	buildMaxHeapify(nums, heapSize);  
	
	//swap将每次排序后的最大值放置到当前队尾，形成从小到大排序
	for(int i=nums.size()-1; i>=1; i--)
	{
		swap(nums[0], nums[i]);
		heapSize--;
		maxHeapify(nums, 0, heapSize);
	}
}