八大排序之堆排序

一、堆排序的思想
堆排序是选择排序的一种，它满足完全二叉树。
堆又分为大顶堆和小顶堆。
大顶堆：堆顶元素大于左右孩子的数据（升序）。
小顶堆：堆顶元素小于左右孩子的数据（降序）。
对于堆排序，我们只比较父亲和孩子的关系。
堆排序就是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆， 这样就会得到n个元素中的次小值。如此反复执行,便能得到一个有序序列了。 本篇博客主要说一下大顶堆的实现和排序过程
二、图解大顶堆
给出一组数据
[12，3，21，32，1，34，12，35，34，18]

处理大顶堆的时候一般是从后向前排序。
如何实现大顶堆的排序的呢？
第一步：我们先将堆顶元素与最后一个元素进行交换，然后将除9号下标以外的所有元素重新构成一个大顶堆，最后将9号元素剔除。如下图所示：

第二步：继续将堆顶元素与8号元素进行交换。此时8号元素是第二大的元素。然后继续将剩余元素再进行大顶堆的排序，再将8号下标的元素剔除。如下图所示：

第三步：将堆顶元素和7号下标的元素进行交换，这个时候我们就找到了第三大的数据，然后将除7号下标元素以外的元素进行大顶堆的排序。如下图所示：

然后继续进行堆调整，步骤如上：每次将排序好的大顶堆的堆顶元素与下标从9到1的顺序进行交换再重新排列，最后形成一个升序后的完全二叉树，如下图所示：

这是最后升序后的二叉树。这个整个过程就可以将堆元素排列有序
最后一个父亲结点的计算方式：

（len - 1 - 1）/2

已知父亲结点求左孩子：

2*i + 1

右孩子:

2*i + 2

三、代码实现

void ShowArr(int arr[],int len)
{
	int i = 0;
	for(; i < len;i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void HeapAdjust(int arr[],int  i,int len)
{
	int j = 2 * i + 1;
	int  tmp;
	for(j ; j <len;j = 2*i+1)
	{
		if((j < len - 1)&& (arr[j + 1]) > arr[j])
		{
			j ++;
		}
		if(arr[i] > arr[j])
		{
			break;
		}
	tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
	i = j;//i父亲结点的位置  标识到左右孩子中发生调整的支路
	}
}
void HeapSort(int arr[],int len)
{
	int i = (len - 2) / 2;
	for(i; i >= 0;i--)//形成大顶堆
	{
		HeapAdjust(int arr[], i, len);
	}
	ShowArr(arr,len);
	for(i = len - 1;i > 0;i++)//大顶堆如何排序
	{
		tmp = arr[i];
		arr[i] = arr[0];
		arr[0] = tmp;
		HeadAdjust(arr,0,i);
	}
}

四、堆排序的分析
1、时间复杂度：O(n*log(2)n)
2、空间复杂度：O(1)
3、稳定性：不稳定