灵感来源于YouTube一段根据堆排序(HeapSort)改编的舞蹈而来
#include<stdio.h> void swap(int tree[],int i,int j)//交换数值函数 { tree[i]=tree[i]+tree[j]-(tree[j]=tree[i]);//交换两值 } void heapify(int tree[],int n,int i)//对数组进行堆处理:n表示共n个数,i表示第i个节点 { if(i>=n) return; int c1=2*i+1; int c2=2*i+2; int max=i; if(c1<n&&tree[c1]>tree[max]) max=c1; if(c2<n&&tree[c2]>tree[max]) max=c2; if(max!=i) //如果max仍然是i没有变化,就不需要交换了 { swap(tree,i,max); heapify(tree,n,max); } } void build_heap(int tree[],int n)//创建堆 { int last_node=n-1; int parent_node=(last_node-1)/2; for(int i=parent_node;i>=0;i--)//从最后一个非叶子节点开始进行堆操作 heapify(tree,n,i); } void heapSort(int tree[],int n)//对堆进行堆处理操作 { build_heap(tree,n); for(int i=n-1;i>=0;i--) { swap(tree,0,i); heapify(tree,i,0); } } void print(int a[],int n) { for(int i=0;i<n;i++) printf("%d\t",a[i]); } int main(){ int a[8]={8,1,2,4,5,7,3,6}; int n=8; heapSort(a,n); print(a,n); }
原文:https://www.cnblogs.com/oldfish123/p/13171035.html