数据结构之排序-堆排序

一.堆排序原理：堆排序是基于完全二叉树的选择排序，将二叉树排序为顶堆（大顶堆或者小顶堆），然后将堆顶的元素（也就是最值）交换到指定位置，循环构建顶堆与交换这两个过程直至排序结束；原理如下图：

二.顶堆名词的解释：就是二叉树中所有父结点的值大于或者小于孩子节点的值；

对一个杂乱数据构建大顶堆，得从最下面一个有孩子的节点开始，一般从n/2index开始，

第一步的结果为：6,8,4,7,10,9,5；

第二步的结果为：6,8,9,7,10,4,5；

第三步的结果为：6,10,9,7,8,4,5；

第四步的结果为：10,8,9,7,6,4,5；

最终构成一个大顶堆；

三.排序函数中的选择排序：

每一次都是将排到顶端的最大值交换到相对的最后位置，然后最后位置向前推一位，再构建顶堆；

第一次排序结果为：5,8,9,7,6,4,10；

第二次构建顶堆结果为：9,8,5,7,6,4,10；

第二次排序结果为：4,8,5,7,6,9,10；

第三次构建顶堆结果为：8,7,5,4,6,9,10;

第三次排序结果为:6,7,5,4,8,9,10；

第四次构建顶堆结果：7,6,5,4,8,9,10；

第四次排序结果：4,,6,5,7,8,9,10；

第五次构建顶堆结果为：6,4,5,7,8,9,10;

第五次排序结果为：5,4,6,7,8,9,10；

第六次排序结果为：4,5,6,7,8,9,10;

最终排序结果为：4,5,6,7,8,9,10

四.程序代码区：

//堆排序是选择排序的改进版
//原理:利用完全二叉树的性质，将数调成顶堆，然后交换顶和尾没再进行调换，依次操作实现排序。
#include<iostream>
using namespace std;

void heap_sort(int a[], int n);
void heapAdjust(int a[],int s,int n);
void heapAdjust1(int a[], int s, int n);

int main()
{
	int a[10] = { 1,5,3,6,2,4,8,9,7,0 };
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	heap_sort(a, 10);
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
	system("pause");
}

//构成一个大顶堆
void heapAdjust(int a[],int s,int n)
{
	int temp,i;
	temp = a[s];					//保存a[s];
	for (i = 2 * s+1; i <= n ; i = 2 * i+1)		//注意死循环，你是由下标为零的时候开始的
	{
		if (a[i] < a[i + 1] && i < (n - 1))//找出孩子中的最大值，然后与父亲比较；
			i++;
		if (temp > a[i])				//判断父亲和孩子的大小关系
			break;
		else
		{
			a[s] = a[i];					//如果父亲比孩子小，则将孩子的最大值赋给父亲
			s = i;							//将孩子的下标赋给s
		}
	}								
	a[s] = temp;						//然后将父亲的值赋给孩子
}

//构成一个小顶堆
void heapAdjust1(int a[], int s, int n)
{
	int temp, i;
	temp = a[s];					//保存a[s];
	for (i = 2 * s + 1; i <= n; i = 2 * i+1)		//注意死循环，你是由下标为零的时候开始的
	{
		if (a[i] > a[i + 1] && i < (n - 1))//找出孩子中的最大值，然后与父亲比较；
			i++;
		if (temp < a[i])				//判断父亲和孩子的大小关系
			break;
		else
		{
			a[s] = a[i];					//如果父亲比孩子小，则将孩子的最大值赋给父亲
			s = i;							//将孩子的下标赋给s
		}
	}
	a[s] = temp;						//然后将父亲的值赋给孩子
}

void heap_sort(int a[], int n)//原理：就是调成顶堆，然后将顶换走，在对余下的调成大顶堆。
{
	for (int k = n / 2; k >=0; k--)//从最后一个右孩子的节点开始排顶堆，然后一直往上调整，把每一个有孩子的节点都调整为大顶堆。
		heapAdjust(a, k, n);

	for (int j = n - 1; j >=0; j--)
	{
		swap(a[0], a[j]);
		heapAdjust(a, 0, j-1);//因为前面已经将堆王权排序为顶堆，后面只是掉了一个数据，所以只需一次调整
	}
}