当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 编程开发堆排序问题C语言版

编程开发堆排序问题C语言版

2018年09月29日  | 移动技术网IT编程  | 我要评论

建平县红山在线,ca1516,人生需要揭穿

afxstd.h
#pragma once
#ifndef afxstd_h
#define afxstd_h
#include
#include
#include
#endif // !afxstd_h

heap.h
#pragma once
#include"afxstd.h"
#ifndef heap_h
#define heap_h
void heapsort(int *arr, int length);
void meakheap(int *arr, int length);
void adjustheap_down(int *arr, int start, int end);
void adjustheap_up(int *arr, int start);
void swap(int *arr, int a, int b);
#endif // !heap_h
heap.cpp
#include"heap.h"
void meakheap(int *arr, int length)
{
	if (arr == null)
	{
		return;
	}
	for (int i = (length -1)/2; i >= 0; i--)/*从第一个非叶子节点从下至上,从右至左调整结构*/
	{
		
		adjustheap_down(arr, i, length - 1);  /*调整函数中传入了数组,起始坐标,末尾坐标*/
	}
}
void heapsort(int *arr,int length) /*排序函数中是传入了数组的长度length*/
{
	if (arr==null)
	{
		return;
	 }
	for (int i=(length-1)/2;i>=0;i--)
	{
		/*从第一个非叶子节点从下至上,从右至左调整结构*/
		adjustheap_down(arr,i,length-1);  /*调整函数中传入了数组,起始坐标,末尾坐标*/
	}
	/*调整堆结构,交换顶端元素与末端元素*/
	for (int j=length-1;j>0;j--)
	{
		swap(arr,0,j);
		adjustheap_down(arr,0,j-1);
	}
}

void swap(int *arr, int a, int b)
{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}
//adjustheap_down,向下调整函数.作用是将数组转化为逻辑上的大堆,
//从而方便升序排序,如果要降序排序,该制堆函数将数组转化为小堆即可.
void adjustheap_down(int *arr, int start, int end)
{
	int i = start;
	int j = 2 * i + 1;
	int temp = arr[i];
	while (j <= end)
	{
		if (j + 1 <= end && arr[j]temp)
		{
			arr[i] = arr[j];
			i = j;
			j = 2 * i + 1;
		}
		else
		{
			break;
		}
	}
	arr[i] = temp;
}
//up,向下调整函数.作用是向上回溯使其符合小堆,也可稍作修使其符合大堆.
void adjustheap_up(int *arr, int start)
{
	int i = start;
	int j = (start-1)/2;
	int temp = arr[i];
	while (j >=0)
	{
		
		if (arr[j]>temp)
		{
			arr[i] = arr[j];
			i = j;
			j = (j - 1) / 2;
		}
		else
		{
			break;
		}
	}
	arr[i] = temp;
}

main.cpp
#include"perioryqueue.h"
int main()
{
	int  arr[] = { 8,18,12,34,90,56,45,78 };
	for (int i = 0; i<8; i++)
	{
		printf("%d\t", arr[i]);
	}
	heapsort(arr, sizeof(arr) / sizeof(arr[0]));
	printf("\n");
	for (int i = 0; i<8; i++)
	{
		printf("%d\t", arr[i]);
	}
	
	return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网