duipaixu.cpp

vc++实现堆排序功能

// DUIPAIXU.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define MAXSIZE  100 // 待排顺序表最大长度
typedef  int  KeyType;    // 关键字类型为整数类型
typedef  struct {
     KeyType   key;              // 关键字项
} RcdType;                         // 记录类型
typedef  struct {
     RcdType r[MAXSIZE + 1];   // r[0]闲置
     int length;                   // 顺序表长度
} SqList;   // 顺序表类型
typedef  SqList  HeapType;
HeapType H1;     
void Creat(SqList &L,int n)
{
	L.length = n + 1;
	int i = 0,l = 0;
	L.r[i].key = 0;
	for(i = 1;i < L.length;i++)
	{
		printf("请输入静态表元素[%d]:",i);
		scanf("%d",&l);
		L.r[i].key = l;
	}
}
void Swap(RcdType &a,RcdType &b)
{
	RcdType t;
	t = a;
	a = b;
	b = t;
}
void HeapAdjust (HeapType &H, int s, int m)// 已知 R[s..m]中记录的关键字除 R[s] 之外均满足堆的特征，本函数自上而下调整 R[s] 的关键字，使 R[s..m] 也成为一个大顶堆
{    
	int j = 0;
	RcdType rc;
	rc = H.r[s];                         // 暂存 R[s] 
	for(j = 2 * s;j <= m;j *= 2 ) // j 初值指向左孩子自上而下的筛选过程;
	{  
		if (j < m && H.r[j].key < H.r[j + 1].key )  
			++j;     // 左/右“子树根”之间先进行相互比较
		if (rc.key >= H.r[j].key )  
			break; // 再作“根”和“子树根”之间的比较，若“>=”成立，则说明已找到 rc 的插入位置 s ，不需要继续往下调整令 j 指示关键字较大记录的位置
		H.r[s] = H.r[j];  
		s = j;   // 否则记录上移，尚需继续往下调整
	}
	H.r[s] = rc;       // 将调整前的堆顶记录插入到 s 位置
} // HeapAdjust

void HeapSort(HeapType &H)  //对顺序表H进行堆排序
{ 
	int i = 0;
	for (i = H.length / 2;i > 0;--i)  //把H.r[1..H.Length]建成大堆顶
		HeapAdjust(H,i,H.length);
	for (i = H.length;i > 1;--i)
	{
		Swap(H.r[1],H.r[i]);     //将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换;
		HeapAdjust(H,1,i-1);  //将H.r[1..i-1]重新调整为大堆顶
    }
}

int main(int argc, char* argv[])
{
	int length = 0;
	printf("请输入静态表长度:\n");
	scanf("%d",&length);
	Creat(H1,length);
	HeapSort(H1);
    printf("排序后的结果为:\n");
	for(int i = 1;i < H1.length;i++)
	{
		printf("%4d",H1.r[i]);
	}
	printf("\n");
	return 0;
}