堆排序算法及C语言实现

堆排序算法的时间复杂度是O(nlgn),比插入排序要好,跟归并排序相同,但是与归并排序不一样的地方在于,堆排序不需要额外的存储空间,或者说,只需要常数个额外的存储空间,属于内排序算法。

有关插入排序和归并排序,请参照:

插入排序及C语言实现归并排序及C语言实现

原理是构造最大堆,并将根节点(最大值)放到数组有效最后位,直到堆节点数量为1。


#include <stdio.h>

int parent(int i);
int left(int i);
int right(int i);
void max_heapify(int *a,int i,int len);
void build_max_heap(int *a,int len);
void heapsort(int *a,int len);

main()
{
	int i;
	int a[10] = {32,54,12,7,4,34,67,12,33,10};
	heapsort(a,10);
//	max_heapify(a,2,10);
	//build_max_heap(a,10);
	for (i = 0;i < 10;i++)
		printf("%d  ",a[i]);
	printf("\n");
}

int parent(int i)
{
	return i/2;
}
int left(int i)
{
	return 2*i;
}
int right(int i)
{
	return 2*i+1;
}
void max_heapify(int *a,int i,int len)
{
	int l,r,largest,heap_size;
	l = left(i);
	r = right(i);
	heap_size = len;
	if (l <= heap_size && a[l-1] > a[i-1])
		largest = l;
	else largest = i;
	if (r <= heap_size && a[r-1] > a[largest-1])
		largest = r;
	if (largest != i) {
		a[i-1] = a[i-1] ^ a[largest-1];
		a[largest-1] = a[i-1] ^ a[largest-1];
		a[i-1] = a[largest-1] ^ a[i-1];
		max_heapify(a,largest,len);
	}
}
void build_max_heap(int *a,int len)
{
	int heap_size,i;
	heap_size = len;
	for (i = len/2;i >= 1;i--)
		max_heapify(a,i,heap_size);
}
void heapsort(int *a,int len)
{
	int i,heap_size;

	heap_size = len;
	build_max_heap(a,heap_size);
	for (i = heap_size;i >= 2;i--) {
		a[0] = a[0] ^ a[i-1];
		a[i-1] = a[0] ^ a[i-1];
		a[0] = a[0] ^ a[i-1];
		heap_size--;
		max_heapify(a,1,heap_size);
	}
}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。