首页 > 代码库 > 堆排序
堆排序
先看下堆的概念:堆是一种数据结构,逻辑上是一种完全的二叉树,在存储上是数组对象。
堆分为小顶堆和大顶堆,顾名思义:小顶堆是指顶部的元素是最小的,大顶堆是指顶部的元素师最大的。
这样只要我们能够得到这样的堆,每次将顶部的元素和数列的最后一个元素进行交换,然后再对剩下的元素进行建堆,接着以此类推这样的做法,便可以得到排好的数列了。
根据上面所述,堆排序的关键是:建堆。建堆也分为调堆和建堆过程;
调堆的过程是:比较一个节点和他的子节点的大小,将最小的或者最大的数和父节点交换,交换后的子节点再接着当做父节点做同样的比较,知道不需要交换为止;代码如下:
void _adjust_heap(int *A,int size,int element) { int left=2*element+1; int right=left+1; int min=0; while(left<size) { min=left; if(right<size) { if(A[min]>A[right]) min=right; } if(A[element]>A[min]) swap(A[element],A[min]); else break; element=min; left=2*element+1; right=left+1; } }</span>
建堆的过程是:对堆的非叶子节点进行调堆,就完成了建堆的过程。
void _build_heap(int *B,int size) { for(int i=size/2-1;i>=0;i--) { _adjust_heap(B,size,i); } }</span>
排序的过程:对数组进行建堆,每次将第一个元素和最后一个元素交换,然后数组的规模减一,再建堆,直到只剩下一个元素为止。
void _sort(int *A,int size) { int length=size; for(;length>=1;length--) { _build_heap(A,length); swap(A[length-1],A[0]); } }</span>
编写程序进行测试:
void main() { int ia[]={0,3,2,6,2,9,2,3,1}; int size=sizeof(ia)/sizeof(int); _sort(ia,size); for(int i=0;i<size;i++) { cout<<ia[i]<<endl; } }</span>测试结果为:
堆排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。