堆排序

#include <iostream>
#include <algorithm>
using namespace std;
//创建大顶堆
void build_heap(int a[],int len)
{
	int i=len;
	bool f=false;
	while((i*2)>len)
	{
		int j=i;
		while(j!=1)
		{
			int& c=(int&)(max(a[j/2-1],max(a[j-1],j/2?a[j-2]:a[j])));
			if(c!=(a[j/2-1])){swap(c,a[j/2-1]);f=true;}
			j/=2;
		}
		i-=2;
	}
	if(f)build_heap(a,len);
	else return;
}
//取最大值放在数组末尾，其余元素再进行大顶堆创建
void heap_sort(int a[],int len)
{
	build_heap(a,len);
	while(len>1)
	{
		swap(a[0],a[len-1]);
		swap(a[len-1],a[len]);
		build_heap(a,len--);
	}
	swap(a[0],a[1]);
}

<script>
function buildheap(a,end)
{
for(i=end;i>0;i-=2)
{
    var j=i,tmp,flag=0;
    if(2*(i+1)<=(end+1))break;
    while(j>0)
    {
        var p=parseInt((j+1)/2)-1,l=parseInt((j+1)/2*2)-1,r=parseInt((j+1)/2*2);
        if(a[l]>a[p])
        {
            tmp=a[l];
            a[l]=a[p];
            a[p]=tmp;
            flag=1;
        }
        if(r<=end)
        {
            if(a[r]>a[p]){
            tmp=a[r];
            a[r]=a[p];
            a[p]=tmp;
            flag=1;}
        }
        j=parseInt((j+1)/2)-1;
    }
    if(flag==1)i+=2;
 
}
return a;
}
 
(function heapsort()
{
var arry=new Array(31,2,15,9,21,90,25,81)
arry=buildheap(arry,7);
function heapadjust(end)
{
    var j=0,tmp;
    while((j+1)*2<=(end+1))
    {
    var l=(j+1)*2-1,r=(j+1)*2,p=j;
    if(arry[p]<arry[l] && arry[l]>arry[r])
    {
        tmp=arry[l];
        arry[l]=arry[p];
        arry[p]=tmp;
        j=l;       
    }
    else if(r<=end)
    {
        if(arry[p]<arry[r] && arry[r]>arry[l])
        {
        tmp=arry[r];
        arry[r]=arry[p];
        arry[p]=tmp;
        j=r;
        }
    }
    else break;
    }  
 
}
var end=7;
while(end>0)
{
tmp=arry[0];
arry[0]=arry[end];
arry[end]=tmp;
heapadjust(end-1);
end--;
}
for(i=0;i<8;i++)alert("final array:"+arry[i]);
})();
</script>

 堆排序的思想：把待排序数组看作是一个完全二叉树的顺序存储结构，初始的二叉树不具有堆的性质，因此进行下面的操作之前必须，对树的结点顺序进行调整，使之满足堆的性质，这种调整的基本思想是，数值大的结点上浮