选择排序之堆排序（Heap Sort）

本文主要总结了堆排序相关知识，其中包括堆排序的概念、算法思想、特点和完整实现代码。

堆排序

堆

• 顺序存储地 “ 完全二叉树 ”
  • 结点 i 地左孩子是2i；右孩子是2i+1；父结点是i/2
• 大根堆（根>=左、右）；小根堆（根<=左、右）；

算法思想

• 建堆
  • 编号<= n/2 的所有结点依次 “ 下坠 ”调整（自底向上处理各分支结点）
  • 调整规则：小元素逐层 “ 下坠 ”（与关键字更大的孩子交换）
• 排序
  • 将堆顶元素加入有序子序列（堆顶元素与堆底元素交换）
  • 堆底元素换到堆顶后，需要进行“ 下坠 ”调整，恢复“ 大根堆 ”的特性
  • 上述过程重复 n~1 趟

特性

• 空间复杂度：O(1)
• 时间复杂度：建堆O(n)、排序O(nlogn)；总的时间复杂度= O(nlogn)
• 稳定性：不稳定
• 基于大根堆的堆排序得到 “ 递增序列 ”，基于小根堆的堆排序得到 “ 递减序列 ”

完整实现代码

大根堆：按升序排列

#include<iostream>
#include<string>

using namespace std;

/* 堆排序 */

//将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len)
{
	A[0] = A[k];  //A[0]暂存子树的根结点
	//沿key较大的子结点向下筛选
	for (int i = 2*k; i <= len; i*=2)
	{
		if (i<len&&A[i]<A[i+1]) 
		{
			i++; //取key较大的子结点的下标
		}
		if (A[0]>=A[i])
		{
			break;//筛选结束
		}
		else 
		{
			A[k] = A[i]; //将A[i]调整到双亲结点上
			k = i;  //修改k值，以便继续向下筛选
		}
	}
	A[k] = A[0];//被筛选结点的值放入最终位置
}

//建立大根堆
void BuildMaxHeap(int A[], int len)
{
	//从后往前调整所有非终端结点
	for (int i = len / 2; i > 0; i--)
	{
		HeadAdjust(A, i, len);
	}
}

//堆排序
void HeapSort(int A[],int len)
{
	BuildMaxHeap(A,len);  //初始建堆
	for (int i = len; i > 1; i--) //n-1 趟的交换和建堆过程
	{
		swap(A[i], A[1]);   //堆顶元素和堆底元素交换
		HeadAdjust(A, 1, i - 1); //把剩余的待排序元素整理成堆
	}
}

int main()
{
	//有哨兵的数组
	int A[] = {0,3,5,2,6,1,4,9,8 };
	HeapSort(A, 8);
	cout << "堆排序后：" << endl;
	for (int i = 1; i <= 8; i++)
	{
		cout << A[i];
		if (i == 8)
		{
			cout <<endl;;
		}
		else
		{
			cout << ",";
		}
	}
	system("pause");
	return 1;
}

小根堆：按降序排列

修改部分：

//将以k为根的子树调整为小根堆
void MinHeadAdjust(int A[], int k, int len)
{
	A[0] = A[k];  //A[0]暂存子树的根结点
	//沿key较大的子结点向下筛选
	for (int i = 2 * k; i <= len; i *= 2)
	{
		if (i < len && A[i] > A[i + 1]) //大根堆改小根堆第一步把小于号改为大于
		{
			i++; //取key较小的子结点的下标
		}
		if (A[0] <= A[i]) ////大根堆改小根堆第二步把大于等于号改为小于等于
		{
			break;//筛选结束
		}
		else
		{
			A[k] = A[i]; //将A[i]调整到双亲结点上
			k = i;  //修改k值，以便继续向下筛选
		}
	}
	A[k] = A[0];//被筛选结点的值放入最终位置
}

完整实现：

#include<iostream>
#include<string>

using namespace std;

/* 堆排序 */

//将以k为根的子树调整为小根堆
void MinHeadAdjust(int A[], int k, int len)
{
	A[0] = A[k];  //A[0]暂存子树的根结点
	//沿key较大的子结点向下筛选
	for (int i = 2 * k; i <= len; i *= 2)
	{
		if (i < len && A[i] > A[i + 1]) //大根堆改小根堆第一步把小于号改为大于
		{
			i++; //取key较小的子结点的下标
		}
		if (A[0] <= A[i]) ////大根堆改小根堆第二步把大于等于号改为小于等于
		{
			break;//筛选结束
		}
		else
		{
			A[k] = A[i]; //将A[i]调整到双亲结点上
			k = i;  //修改k值，以便继续向下筛选
		}
	}
	A[k] = A[0];//被筛选结点的值放入最终位置
}

//建立小根堆
void BuildMinHeap(int A[], int len)
{
	//从后往前调整所有非终端结点
	for (int i = len / 2; i > 0; i--)
	{
		MinHeadAdjust(A, i, len);
	}
}

//堆排序
void HeapSort(int A[],int len)
{
	BuildMinHeap(A,len);  //初始建堆
	for (int i = len; i > 1; i--) //n-1 趟的交换和建堆过程
	{
		swap(A[i], A[1]);   //堆顶元素和堆底元素交换
		MinHeadAdjust(A, 1, i - 1); //把剩余的待排序元素整理成堆
	}
}

int main()
{
	//有哨兵的数组
	int A[] = {0,3,5,2,6,1,4,9,8 };
	HeapSort(A, 8);
	cout << "堆排序后：" << endl;
	for (int i = 1; i <= 8; i++)
	{
		cout << A[i];
		if (i == 8)
		{
			cout <<endl;;
		}
		else
		{
			cout << ",";
		}
	}
	system("pause");
	return 1;
}