堆排序-C语言

算法思想：

建立一个大根堆;（将一棵普通的树转化为大根堆）
每次将根和待排序的最后一个交换,然后再调整,循环len-1次即可;

调整为大根堆的方法：

从最后一棵子树开始,从后往前调整;
每次调整,从上往下;
调整为大根堆;

堆调整的代码实现：

void  HeapAdjust(int* arr, int start, int end)//堆调整
{
	int  tmp = arr[start];
	for (int i = 2 * start + 1; i <= end; i=2*i+1)
	{
		if (i < end && arr[i] < arr[i + 1])//如果有右孩子,并且左孩子的值小于右孩子
		{
			i++;
		}//i一定是左右孩子的最大值
		if (arr[i] > tmp)
		{
			arr[start] = arr[i];
			start = i;
		}
		else
		{
			break;
		}
	}
	arr[start] = tmp;
}

代码实现：

void   HeapSort(int* arr, int len)//堆排序,O(nlogn),O(1),不稳定
{
	int i;
	//第一次建立大根堆,从后往前,多次调整
	for (i = (len - 1 - 1) / 2; i >= 0; i--)//有一个数学证明,O(n)
	{
		HeapAdjust(arr, i, len - 1);//第一次建立大根堆
	}

	//每次将根和待排序的最后一个交换,然后再次调整
	int  tmp;
	for (i = 0; i < len - 1; i++)  //O(nlogn)
	{
		//交换
		tmp = arr[0];
		arr[0] = arr[len - 1 - i];
		arr[len - 1 - i] = tmp;

		//再次调整
		HeapAdjust(arr, 0, len -1-i  -1);//堆调整
	}
}

效率分析：

时间复杂度:O(nlogn),系数大,空间复杂度O(1),不稳定