数组堆排序

堆排序也是一种空间换时间的做法,速度相对较快,我们需要生成一个动态的临时数组,以二叉堆的格式将数据插入到数组中,表现形式如下图:

2015-06-12_115119

这个二叉堆是一个完全二叉树或一个近似完全的二叉树,要满足以下两点特性:

【二叉堆概念】

  • 父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
  • 每个节点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)

【最大堆最小堆概念】

  • 父节点的键值总是大于或等于子节点的键值时为最大堆(大顶堆)
  • 父节点的键值总是小于或等于子节点的键值时为最小堆(小顶堆)

了解以上概念后,我们就要清楚堆排序的过程了,首先我们要将数据按一定格式(比如按大顶堆或者小顶堆的格式)插入到二叉堆中,在插入过程中要对数据进行对比排序。全部插入完成后,将二叉堆中的根节点的数值依次取出,取出的同时,将堆中最后一个数据覆盖到根节点,再将这个数据与所有子节点对比,最终把最大(或最小)的子节点移动到根节点的位置。这样保证每次取出的数据都是最大(或最小)的数据。表现形式如下:

【插入元素】

插入元素的步骤

  1. 先将此元素插入添加到完全二叉树的最后面的位置(数组的最后), 此完全二叉树多了一个叶子节点.
  2. 求出此叶子节点的父节点, 与其父节点进行比较, 如果比父节点大则二者交换位置
  3. 重复步骤2
  4. 节点插入完成

2015-06-12_120159

【弹出元素】

弹出元素步骤

  1. 删除根节点
  2. 将最后一个叶子节点放到根节点的位置
  3. 新的根节点分别与其左右孩子比较,如果比根节点大, 选出较大的一个
  4. 将根节点与值较大的叶子节点交换位置
  5. 发生交换的孩子节点如果还有子节点, 重复3, 4步

2015-06-12_120518

【实现代码】

#include <stdio.h>
#include <stdlib.h>

typedef struct _tag_heapTag
{
	// 指向数据的指针,用于创建动态数组存储数据
	int *arrList;
	// 记录当前堆中的节点个数
	int nSize;
}MyHeap;

int PopMaxValue(MyHeap* pHeap)
{
	int nPos = 1;
	// 记录根节点最大值,用于返回值
	int nMax = pHeap->arrList[nPos];
	// 把数组最后的值挪动到根节点的位置,并记录下挪动过来的值
	int nTemp = pHeap->arrList[nPos] = pHeap->arrList[pHeap->nSize];

	// 得到根节点的子节点的位置
	int nChild = nPos * 2;
	while (nChild <= pHeap->nSize)
	{
		// 判断右子节点的下标不超过数组长度
		if (nChild + 1 <= pHeap->nSize &&
			// 判断右子节点是否大于左子节点
			pHeap->arrList[nChild] < pHeap->arrList[nChild + 1])
		{
			// 如果右子节点大于左子节点,那么让子节点位置等于右子节点
			nChild++;
		}
		// 根节点的值是最大的,无需交换了
		if (pHeap->arrList[nPos] > pHeap->arrList[nChild])
			break;

		// 如果小于,那么交换子节点和当前根节点的值
		pHeap->arrList[nPos] = pHeap->arrList[nChild];
		// 让根节点等于被交换前原子节点的位置
		nPos = nChild;
		// 计算出交换后节点位置下的子节点的位置,用于下次循环
		nChild *= 2;
	}

	// 退出循环后nPos的位置一定是最下面叶子节点的位置,把之前备份的值赋值给它
	pHeap->arrList[nPos] = nTemp;
	// 数组长度--
	pHeap->nSize--;

	// 返回被删除的数据
	return nMax;
}

int InsertKey(MyHeap* pHeap, int nPos)
{
	while (nPos > 1)
	{
		// 记录下当前nPos节点值
		int nMax = pHeap->arrList[nPos];
		// 父节点下标
		int nParent = nPos / 2;
		if (nMax > pHeap->arrList[nParent])
		{
			// 交换子节点和父节点的值
			pHeap->arrList[nPos] = pHeap->arrList[nParent];
			pHeap->arrList[nParent] = nMax;
			// 记录父节点的位置给nPos,用于下次循环
			nPos = nParent;
		}
		else
		{
			// 子节点已经不大于父节点的值
			break;
		}
	}
	return 0;
}

void Insert(MyHeap* pHeap, int nData)
{
	pHeap->nSize++;
	pHeap->arrList[pHeap->nSize] = nData;
	// 比较,向上渗透
	InsertKey(pHeap, pHeap->nSize);
}

void heapSort(int arr[], int len)
{
	MyHeap myHeap;
	// 给插入数据的数组空间分配内存,因为要跳过下标为0的元素
	// 所以长度要是传递进来的数组长度 + 1的大小
	myHeap.arrList = (int*)malloc(sizeof(int) * (len + 1));
	myHeap.nSize = 0;

	for (int i = 1; i <= len; i++)
	{
		// 一次将数组中的元素插入动态分配的数组
		Insert(&myHeap, arr[i - 1]);
	}

	// 弹出数据并打印弹出的值
	for (int i = 1; i <= len; i++)
	{
		printf("%d ", PopMaxValue(&myHeap));
	}
	// 释放申请的空间
	free(myHeap.arrList);
}

int main(int argc, char* argv[])
{
	int arr[] = { 12, 5, 33, 6, 10 };
	int len = sizeof(arr) / sizeof(int);
	printf("待排序数组序列: ");
	for (int i = 0; i < len; ++i)
	{
		printf("%d\t", arr[i]);
	}
	putchar(10);

	//遍历
	printf("堆排序之后的序列: ");
	heapSort(arr, len);
	putchar(10);
	return 0;
}

 

评论