欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

自己瞎写的堆排序算法(C语言实现)

程序员文章站 2022-06-23 22:06:25
读者朋友,如果你想直接看代码块,可以拉到下面。这里我把我一开始写的,和看了老师的代码后写的,都列出来了,请留意我的备注。自己看了一遍老师画的图示,就想写堆排序。写到是写出来了,也可以正常编译运行,甚至到得出排序结果都没有任何问题。堆排序的算法主要有两个关键之处:1.在无序数组的基础上创建大根堆或小根堆。2.对首位互换后的堆进行调整,使其重新变为标准的大根堆或小根堆。我自己写的算法中,为了解决上述两个问题,写了一个核心的函数,即下面代码块中的SingleExchangeforCreate,主要输入需...

读者朋友,如果你想直接看代码块,可以拉到下面。这里我把我一开始写的,和看了老师的代码后写的,都列出来了,请留意我的备注。

自己看了一遍老师画的图示,就想写堆排序。写到是写出来了,也可以正常编译运行,甚至到得出排序结果都没有任何问题。

堆排序的算法主要有两个关键之处:

1.在无序数组的基础上创建大根堆或小根堆。

2.对首位互换后的堆进行调整,使其重新变为标准的大根堆或小根堆。

我自己写的算法中,为了解决上述两个问题,写了一个核心的函数,即下面代码块中的SingleExchangeforCreate,主要输入需要处理的数组的开始之处的下标,把这个下标的元素与其两个孩子进行比较,如需要,则进行交换。顾名思义,SingleExchangeforCreate就是一次性交换,这个函数每次只处理一个双亲和它的左右孩子。

这个函数本身是没有问题的,但是问题在于实现1和2时,需要以不同的方式调用。

实现1时,我的思路是从i = n/2个元素开始,进行i–,依次对所有的下标为n/2到下标为1的双亲进行操作、与其孩子进行置换。

实现2时,我有两个思路。第一个思路就是上面实现1的思路。我从堆尾开始执行SingleExchangeforCreate一直执行到堆头。这样做总觉得效率会低,但是我又说不出个为啥。另一种思路是递归,即在主函数里调用SingleExchange函数,这个函数与SingleExchangeforCreate相比几乎唯一的区别就是加了递归入口。但是递归效率必然更低,因为还要用到递归工作栈之类的。

再后来我看了老师的写法,感觉清爽了不少。老师用了一个HeapAdjust,输入的参数分别是数组本身,需调整的堆的首下标以及其末下标。这个函数的输入值都这么清晰,即就是要调整这个堆从开始到结束的位置的元素。

我的体会就这些。下面把两份代码块贴上来,供大家参考。其中,函数CreateArray和Display分别是生成随机数组和遍历输出数组的函数,与堆排序本身无关。

下面这个代码块里的代码,是我一开始没怎么看老师的代码时写的。

#include<time.h>
#include<stdlib.h>
#include<stdio.h>
//目的:调整大根堆,把小的数换到底下,把大数放到上面
void CreateArray(int*a, int length)//该函数用于生成无序数组,用以排序 
{
	srand((unsigned)time(NULL));//用当前系统时间设置种子
	for(int i=0;i<100;i++)
	{
		a[i]=rand()%121; //用rand函数生成随机数,并赋值给数组a[i]
	}
}
void InnerExchange(int*a, int x, int y)
{
	int t;
	t = a[x];
	a[x] = a[y];
	a[y] = t;
}
void SingleExchangeforCreate(int*a, int n, int randomlength)//n是当前根结点,randomlength是无序部分的长度 
{
	int t;
	if(2*n<randomlength)//length应为下标 
	{
		if(a[2*n] >a[n]) 
		{
			InnerExchange(a, n, 2*n);
		}
		if(a[2*n+1]>a[n]) 
		{
			InnerExchange(a, n, 2*n+1);
		} 
		
	}
	else if(2*n==randomlength)
	{
		if(a[2*n]>a[n]) 
		{
			InnerExchange(a, n, 2*n);
		}
	}
}
void SingleExchange(int*a, int n, int randomlength)//n是当前根结点,randomlength是无序部分的长度 
{
	int t;
	if(2*n<randomlength)//length应为下标 
	{
		if(a[2*n] >a[n]) 
		{
			InnerExchange(a, n, 2*n);
			SingleExchange(a, 2*n, randomlength);
		}
		if(a[2*n+1]>a[n]) 
		{
			InnerExchange(a, n, 2*n+1);
			SingleExchange(a, 2*n+1, randomlength);
		} 
		
	}
	else if(2*n==randomlength)
	{
		if(a[2*n]>a[n]) 
		{
			InnerExchange(a, n, 2*n);
			SingleExchange(a, 2*n, randomlength);
		}
	}
}
void CreateHeap(int*a, int length)//length应为下标,即接受的值应该比数组长度大1 
{
	for(int j = length/2; j>=1; j--)
	{
		SingleExchangeforCreate(a, j, length);
	}
}
void HeapSort(int*a, int length)//length应为下标,即接受的值应该比数组长度大1 
{
	CreateHeap(a, length);
	while(length!=1)
	{
		a[0]= a[1];
		a[1] = a[length];
		a[length--] = a[0];
//		for(int j = length/2; j>=1; j--)
//		{
//			SingleExchange(a, j, length);
//		}
		SingleExchange(a,1,length);
	}
}
void Display(int *a, int length)
{
	for(int i=0; i<length; i++)
	{
		printf("%4d", a[i]);
		if(i%10==9) putchar('\n');
	}
}
int main(void)
{
	int a[100];
	CreateArray(a, sizeof(a)/sizeof(a[0]));
	Display(a, sizeof(a)/sizeof(a[0]));
	puts("\n\n");
	HeapSort(a, sizeof(a)/sizeof(a[0])+1);
	Display(a, sizeof(a)/sizeof(a[0]));
	return 0;
}

下面这个代码块里的代码,是我看了老师的代码后写的。

#include <time.h>
#include <stdlib.h>
#include <stdio.h>
//目的:调整大根堆,把小的数换到底下,把大数放到上面,这样,就可以从小到大排序 
void CreateArray(int*a, int length)//该函数用于生成无序数组,用以排序 
{
	srand((unsigned)time(NULL));//用当前系统时间设置种子
	for(int i=0;i<100;i++)
	{
		a[i]=rand()%121; //用rand函数生成随机数,并赋值给数组a[i]
	}
}
void HeapAdjust(int*a, int imin, int imax)//imin = MIN(the index of the array) and imax = MAX(the index of the array)
{
	a[0] = a[imin];//use a[0] to temporarily restore a[imin] 
	for(int j = 2*imin; j<=imax; j*=2)
	{
		if(j<imax && a[j]<a[j+1]) j++;
		if(a[j]<a[0]) break;
		a[imin] = a[j]; imin = j;
	}
	a[imin] = a[0];
} 
void HeapCreate(int*a, int imax)
{
	for(int i=imax/2; i>=1; i--)
	{
		HeapAdjust(a, i, imax);
	}
}
void Swap(int* a, int imax)
{
	a[0] = a[imax];
	a[imax] = a[1];
	a[1] = a[0];
}
void HeapSort(int*a, int imax)
{
	HeapCreate(a, imax);
	while(imax>1)
	{
		Swap(a, imax--);//把数组a中下标为1的元素与下标为imax的元素进行互换 
		HeapAdjust(a, 1, imax); 
	}
} 

void Display(int *a, int length)
{
	for(int i=0; i<length; i++)
	{
		printf("%4d", a[i]);
		if(i%10==9) putchar('\n');
	}
}

int main(void)
{
	int a[100];
	CreateArray(a, sizeof(a)/sizeof(a[0]));
	Display(a, sizeof(a)/sizeof(a[0]));
	puts("\n\n");
	HeapSort(a, sizeof(a)/sizeof(a[0])+1);
	Display(a, sizeof(a)/sizeof(a[0]));
	return 0;
}

本文地址:https://blog.csdn.net/weixin_44582771/article/details/107301066