堆排序的数组实现

数组实现：

</pre><p><span style="font-size:14px"></span></p><pre name="code" class="cpp">#include "stdafx.h" 
#include<iostream>
using namespace std;


void adjustHeap(int a[],int index,int length)
{
     int record = a[index];
     for(int j = 2*index;j<length;j*=2)//
     {
             if(a[j]<a[j+1])//找到较大的儿子
             {
                   j = j+1;
             }
             if(record>a[j])//如果record比a[j]大，那表示不需要再往下找合适的地点放置record了
             {
                   break;
             }
//如果record比当前的a[j]小，那么还需要继续往下层寻找record应该放置的地点
             a[index] = a[j];
             index = j;
     }
     a[index] = record;    
}


void add(int *a,int size,int val)//往堆里插入一个元素，使其仍然保持有序
{


     //*(a+size) = 100;
     //display(a,size);
     int tmp = size;//tmp表示应该插入的位置
     int parent = tmp/2;
     while(parent>0)
     {
        if(*(a+parent) > val)//如果父节点比val大，那么表示val不可能再往上升了。
                       break;
        *(a+tmp) = *(a+parent);//如果父节点比val小，说明val还应该往上升，才能调整成为大根堆
        tmp = parent;
        parent = tmp/2;
     } 
     *(a+tmp) = val;
}


void display(int a[], int len)
{
     for(int i=1;i<len;i++)
             cout<<a[i]<<" ";
     cout<<endl;
}
int main()
{   int a[20] = {0,49,38,65,97,76,13,27,49}; 
    int len = 9;
    display(a,len);
    for(int i=len/2;i>0;i--)//从最后一个非叶子节点开始调整
    {
            adjustHeap(a,i,len);
    }
add(a,len,100);
len++;
    display(a,len);
    for(int i=0;i<len-1;i++)//交换树根和最后一个叶子节点，这样最大的数就到数组最后去了，然后在调整前面的未排序节点
    {
            int tmp = a[1];
            a[1] = a[len-1-i];
            a[len-1-i] = tmp;
            adjustHeap(a,1,len-2-i);
    }
    display(a,len);
    getchar();
    return 0;
}
</pre><p><span style="font-size:1