设为首页 加入收藏

TOP

编程开发堆排序问题C语言版
2018-06-28 19:43:47 】 浏览:153
Tags:编程 开发 排序 问题 语言
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;
}

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇数组名、数组地址、数组首字节地.. 下一篇C语言函数调用栈的详细教程

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目

array(4) { ["type"]=> int(8) ["message"]=> string(77) "Use of undefined constant bencandy_cache_time - assumed 'bencandy_cache_time'" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(207) }