算法导论——堆排序

#include<stdio.h>
#include<iostream>

using namespace std;
#define Length 10


void MaxHeapify(int num[], int i, int len);
void BuildHeap(int num[], int len);
int Heapsort(int num[], int len);
 
void Output(int num[], int length);


int main ()
{
	int num[Length] = {12, 2, 34, 56, 26, 8, 31, 6, 20, 3};
	BuildHeap(num, Length);
	Heapsort(num, Length);
	Output(num, Length);
}

//堆排序的关键是一定要搞清楚len 在每个函数中的不同值 是长度还是下标 
int Heapsort(int num[], int len)//此处的len代表的是实际长度 
{
	int t;
	for(int i = len - 1; i >= 1; i--)//在堆排序的过程中0位存储的是最大值 因此每次进行排序的时候都将0位的元素和最后一位进行交换 
	{
		t = num[i];
		num[i] = num[0];
		num[0] = t;
		len--;//每执行一次就可以得到高位的一个元素 此时len应该-1 即每次执行的长度是递减的 
		MaxHeapify(num, 0, len - 1); //一定是len - 1!!! 因为在MaxHeapify中 第三个参数代表的是数组的角标  比实际长度小1 
	}
}
//BuildHeap只是用一次 即构建初始堆 因为之后的对调整函数需要在初始堆的基础上进行操作 
void BuildHeap(int num[], int len)//建堆  len是长度  利用给定的数组num 
{
	for(int i = len/2; i >= 0; i--)//i的初始值是 len/2向下取整  利用的是二叉树中双亲结点与子节点之间的下标关系 
	{
		MaxHeapify(num, i, len - 1);//在MaxHeapify中 
	}//for循环结束后 就构建好了初始堆 
}

//这个函数的作用是调整堆 
void MaxHeapify(int num[], int i, int len)//见图Heapsort 
{
	int left = 2 * i;//left是i的左孩子的下标  由二叉树的性质可以知道 
	int right = 2 * i + 1;
	int largest, t;
	
	//下面几行语句的作用是在i以及i的左右孩子中找到最大值 并将其位置保存在largest中 
	if(left <= len && num[left] > num[i])
	largest = left;
	else
	largest = i;
	
	if(right <= len && num[right] > num[largest])
	largest = right;
	
	if(largest != i)//满足if条件则说明 i的其中一个子节点大于它 并将出现交换的操作 
	{
		t = num[i];
		num[i] = num[largest];
		num[largest] = t;
		MaxHeapify(num, largest, len);//交换之后需要重新判断原i的值是否比原largest的全部子节点的值都大 
	}
} 

void Output(int num[], int len)
{
    for(int i=0; i<len; i++)
    {
        printf("%d  ", num[i]);
    }
    cout << endl;
}