堆排序算法思路详解

    堆排序是一种常见的排序算法，其时间复杂度为O(logN)，重要思想为建堆取极值，根据需求进行排序，如下图：

    值得思考的是，二次建堆的过程中，实际上是没有必要将所有元素都进行下调，只需要将根进行下调：

    实现代码如下：

template <class T>//建立仿函数模板满足排序需求 struct CompMax {	bool operator()(const T& a, const T& b)	{	return a > b;	} }; template <class T> struct CompMin {	bool operator()(const T& a,const T& b)	{	return a < b;	} }; template <class T ,class Com = CompMax<T> > static void HeapSort(vector<T>&list) {	size_t size = list.size();	GetHeap<T>(list, size);	swap(list[0], list[size - 1]);	while (--size > 1)	{	adjustdown<T>(0, size, list);	swap(list[0], list[size - 1]);	} } template <class T,class Com = CompMax<T> > void adjustdown(int index, size_t size, vector<T>&list) {	Com comp;	size_t parent = index;	size_t child = parent * 2 + 1;	while (child < size)	{	if (child + 1 < size)	child = child = comp(list[child], list[child + 1]) ? child : child + 1;	if (!comp(list[parent], list[child]))	{	std::swap(list[child], list[parent]);	parent = child;	child = parent * 2 + 1;	}	else	break;	} } template <class T ,class Com = CompMax<T> > static void GetHeap(vector<int>&list, size_t size) {	size_t parent = (size - 2) / 2;	int begin = parent;	Com comp;	while (begin >= 0)	{	size_t child = parent * 2 + 1;	while (child<size)	{	if (child + 1<size)	child = child = comp(list[child], list[child + 1]) ? child : child + 1;	if (!comp(list[parent], list[child]))	{	swap(list[child], list[parent]);	parent = child;	child = parent * 2 + 1;	}	else	break;	}	parent = --begin;	} }

    如有不足，希望指正，有疑问也希望提出