heapsort.cpp

随机生成500个数字并进行快速排序

#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "sys/timeb.h"

typedef int KeyType;		// 定义关键字类型为整数类型

#define MAXSIZE   500		// 数组的最大容量
#define LT(a,b)   ((a)<(b))
#define OUTFORMAT "%10d"	// 输出格式控制符

typedef struct
{
	KeyType key;			// 关键字项,若有其它数据项可以这里添加
}RedType;

typedef struct
{
	RedType r[MAXSIZE+1];	// r[0]闲置
	int length;				// 顺序表的长度
}SqList;

void CreateSqList(SqList &L)	// 创建顺序表
{
    int i=1;
	srand((unsigned)time(NULL));// 初始化随机数产生器
    printf("    堆排序\n\n随机产生 %d 个数据:\n\n",MAXSIZE);
	while(i<=MAXSIZE)
	{
		L.r[i].key=rand();		// 获得随机数
		printf(OUTFORMAT,L.r[i].key);
		i++;
	}
	L.length=MAXSIZE;
}

void HeapAdjust(SqList &H,int RecLocal,int NowLength)	// 整堆
{
    RedType rc;
    int j;		// j为孩子下标
    rc=H.r[RecLocal];	// 暂存
    for(j=2*RecLocal;j<=NowLength;j*=2)
    {
		if(j<NowLength&&LT(H.r[j].key,H.r[j+1].key)) ++j;	// 找出左、右孩子中的大者
		if(!LT(rc.key,H.r[j].key)) break;	// 若"根"大,则不进行交换(因建大根堆)
		H.r[RecLocal]=H.r[j];	// 孩子移至根上
		RecLocal=j;				// 继续调整不平衡的堆
    }
    H.r[RecLocal]=rc;	// 归位
}

void HeapSort(SqList &H)	// 堆排序程序的具体实现
{
    int i;
    RedType temp;
    for(i=H.length/2;i>0;--i)		// 建大根(顶)堆
		HeapAdjust(H,i,H.length);
    for(i=H.length;i>1;--i)
    {
		// 将堆顶记录和当前未经排序子序列中的最后一个记录相互交换
		temp=H.r[1];
		H.r[1]=H.r[i];
		H.r[i]=temp;
		HeapAdjust(H,1,i-1);		// 重新调整为大根(顶)堆
    }
}

void main(void)
{
    struct _timeb timebuffer;
	time_t Start,End;					// 秒级
	unsigned short StartTime,EndTime;	// 毫秒级
	time(&Start);			// 获得当前时间(秒)
	_ftime(&timebuffer);	// 获得当前时间(毫秒)
	StartTime=timebuffer.millitm;
	int i;
    SqList L;
	system("cls");			// 清屏
    CreateSqList(L);		// 初始化顺序表
    HeapSort(L);			// 对顺序表L作堆排序
    printf("\n\n排序结果如下所示:\n\n");
    for(i=1;i<=L.length;i++)// 显示出最终结果
		printf(OUTFORMAT,L.r[i].key);
    time(&End);				// 再次获得当前时间(秒)
	_ftime(&timebuffer);	// 再次获得当前时间(毫秒)
	EndTime=timebuffer.millitm;
	if(EndTime>=StartTime)
		printf("\n\n\t\t\t    共耗时 %.0f 秒 %hu 毫秒 !\n",\
		difftime(End,Start),EndTime-StartTime);
	else
		printf("\n\n\t\t\t    共耗时 %.0f 秒 %hu 毫秒 !\n",\
		difftime(End,Start)-1,1000+EndTime-StartTime);
    system("pause");	// 暂停
}