314-Leetcode 堆排序

算法：从最后一颗子树开始从后往前调整，每次调整从上到下，调整为大根堆

为什么从后往前调整，每次调整从上到下？因为如果后前往后调整，那么下面较大的数字永远都不会调整到前面，也就无法调整为大根堆

为什么调整成大根堆？因为每次调整完以后，根就是所有数据中最大的，然后将根和待排序序列的最后一个元素进行交换，最终就完全有序了

如果让求第一大的数、第二大的数，那么就可以使用堆排序

时间复杂度O(nlogn)，空间复杂度O(1)，不稳定

一次堆排序HeapAdjust的时间复杂度为O(logn)，一共需要排序
n次

void HeapAdjust(vector<int>& vec,int start,int end)
{	
	int tmp = vec[start];
	for (int i = start * 2 + 1; i <= end; i=i*2+1)
	{
		if (i<end && vec[i]<vec[i+1])
		{
			++i;
		}
		if (vec[i] > tmp)
		{
			vec[start] = vec[i];
			start = i;
		}
	}
	vec[start] = tmp;
}
void HeapSort(vector<int>& vec)
{
	int len = vec.size();
	int tmp;
	for (int i = (len - 1 - 1) / 2; i >= 0; --i)
	{
		HeapAdjust(std::ref(vec), i, len - 1);
	}
	for (int i = 0; i < len - 1; ++i)
	{
		tmp = vec[0];
		vec[0] = vec[len - 1 - i];
		vec[len - 1 - i] = tmp;
		HeapAdjust(std::ref(vec), 0, len - 1 - i - 1);
	}
}
int main()
{
	vector<int> vec{ 12,89,67,23,34,78,56,45,100,90 };
	HeapSort(std::ref(vec));
	for (auto& x : vec)
	{
		cout << x << endl;
	}
	return 0;
}