1. 堆是满足这样特性的数据结构:1.父结点的键值总是大于等于(或者小于等于)任何一个结点的值2.每个结点的左子树和右子树都是一个二叉树
最大堆是父结点的键值总是大于等于子结点键值的二叉堆,最小堆是父结点的键值总是小于等于子结点键值的二叉堆。
堆排序的基本思想是:先将待排序数组构造成堆,结点为n1,n2,n3,n4…nk,把堆顶元素(最大值)n1与堆中最后一个元素nk互换位置,此时,结点n1,n2,n3,n4,…n(k-1)可能不是最大堆,这时需要下滤的操作调整顺序,使之成为最大堆。接下来交换n1和n(k-1)的位置,调整堆序,重复进行k-1次,排序结束。
2.堆排序的程序为:
# include <iostream> using namespace std; # include <stdlib.h> int main() { int a[10]={3,34,23,67,9,10,8,12,56,45}; int i=0; void heapsort(int a[],int); heapsort(a,10); for(i=0;i<10;i++) cout<<a[i]<<endl; system("pause"); return 0; } void heapadjust(int a[],int s,int end) //调整顺序,使之成为最大堆 { int tmp=a[s]; int i=2*s+1; while(i<=end) { if((i+1<=end)&&a[i+1]>a[i]) i++; if(a[i]<=tmp) break; a[s]=a[i]; s=i; i=2*s+1; } a[s]=tmp; } void heapsort(int a[],int n) //堆排序 { int i=0,t; for(i=(n-1)/2;i>=0;i--) //建立最大堆 heapadjust(a,i,n-1); for(i=n-1;i>0;i--) //交换a[0]和a[i]并调整顺序 { t=a[0]; a[0]=a[i]; a[i]=t; heapadjust(a,0,i-1); } }3.堆排序分析
堆排序的时间复杂度为O(n*lgn),是不稳定的排序
原文:http://blog.csdn.net/u011608357/article/details/21381701