[算法练习]堆排序的C语言实现

一时失言乱红尘 2022-09-30 12:58 128阅读 0赞

#include <stdio.h>
    
    void heap_sort();
    void max_heap();
    void build_heap();
    int LEFT(),RIGHT();
    
    int length;
    
    int main(){
    	int a[]={4,1,3,2,16,9,10,14,8,7};
    	length=sizeof(a)/sizeof(a[0]);
    	int len=length;
    	int i;
    	printf("before:\t");
    	for(i=0;i<len;i++){
    		printf("%d  ",a[i]);
    	}
    	heap_sort(a);
    	printf("\nafter:\t");
    	for(i=0;i<len;i++){
    		printf("%d  ",a[i]);
    	}
    	getchar();
    }
    
    void heap_sort(int A[]){
    	build_heap(A);
    	while(length>=2){
    		//exchange root and last leaf
    		int temp=A[0];
    		A[0]=A[length-1];
    		A[length-1]=temp;
    		//length <- length-1
    		length--;
    		max_heap(A,0);
    	}
    }
    
    //generate max heap
    void max_heap(int A[],int i){
    	int left=LEFT(i);
    	int right = RIGHT(i);
    	int largest=i;
    	if(A[i]<A[left]&&left<=length-1) largest=left;
    	if(A[right]>A[largest]&&right<=length-1) largest=right;
    	if(i!=largest){
    		int temp=A[i];
    		A[i]=A[largest];
    		A[largest]=temp;
    		max_heap(A,largest);
    	}
    }
    
    void build_heap(int A[]){
    	int i;
    	for(i=length/2-1;i>=0;i--){
    		max_heap(A,i);
    	}
    }
    
    int LEFT(i){
    	return i*2+1;
    }
    
    int RIGHT(i){
    	return i*2+2;
    }

![SouthEast][]

[SouthEast]: /images/20220705/b027d4fa089f484b8b7c7fc0b697db89.png

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关堆排序 C语言实现

堆排序 (Heap Sort) 是一种树形选择排序，在排序过程中，将待排序的记录Data\[1…n\]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子

古城微笑少年丶/ 2022年12月22日 13:30/ 0 赞/ 118 阅读

相关 [算法练习]选择排序的C语言实现

include <stdio.h> int length; void selection_sort(int A[]){ i

港控/mmm°/ 2022年09月30日 14:44/ 0 赞/ 152 阅读

相关 [算法练习]冒泡排序的C语言实现

include <stdio.h> int length; void bubble_sort(int A[]){ int

系统管理员/ 2022年09月30日 14:00/ 0 赞/ 176 阅读

相关 [算法练习]插入排序的C语言实现

include <stdio.h> void insert_sort(); int length; int n=0;

拼搏现实的明天。/ 2022年09月30日 12:59/ 0 赞/ 123 阅读

相关 [算法练习]堆排序的C语言实现

include <stdio.h> void heap_sort(); void max_heap(); void build_hea

一时失言乱红尘/ 2022年09月30日 12:58/ 0 赞/ 129 阅读

相关 [算法练习]快速排序的C语言实现

include <stdio.h> void quick_sort(int A[],int p,int r){ if(p<r){

系统管理员/ 2022年07月05日 15:28/ 0 赞/ 150 阅读

相关 C语言实现堆排序算法

利用堆排序的思想将一个数组按递增的顺序进行排序，将数组的第一个位置空下（下标为0），因为会导致子节点和本身同一个结点（i和2i一致），每次堆排序在下标1的位置放上了

小灰灰/ 2022年06月03日 01:59/ 0 赞/ 174 阅读

相关排序算法c语言描述---堆排序

排序算法系列学习，主要描述冒泡排序，选择排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序等排序进行分析。文章规划：一。通过自己对排序算法本身的理解，对每个方法写

- 日理万妓/ 2022年03月18日 09:40/ 0 赞/ 173 阅读

相关堆排序算法（C#实现）

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。另一种是垃圾收集存储

ゝ一世哀愁。/ 2021年11月26日 16:56/ 0 赞/ 222 阅读

相关排序算法c语言描述---堆排序

排序算法系列学习，主要描述冒泡排序，选择排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序等排序进行分析。文章规划：一。通过自己对排序算法本身的理解，对每个方法写

柔光的暖阳◎/ 2021年11月02日 15:38/ 0 赞/ 367 阅读