堆排序C/C++

/*由小到大排序*/
void Adjust(int a[],int low,int high);
void HeapSort(int a[],int n);

//调整大顶堆
//数组从下标0开始存储数据,对下标为low的元素进行调整，右边界下标为high
void Adjust(int a[],int low,int high)    
{
    int i = low,j = 2*i+1;    //a[j]为a[i]的左孩子
    int temp = a[i];    //记录被调整结点的值
    while(j<=high){
        if(j<high && a[j]<a[j+1])
            j++;        //令j指向较大的孩子
        if(temp<a[j]){
            //保证父结点大于孩子结点
            a[i] = a[j];
            i = j;
            j = 2*i+1;
        }else
            break;
    }
    a[i] = temp;    //被调整结点的值放入最终位置
}

void HeapSort(int a[],int n)
{
    int i;
    int temp;
    //建立大顶堆
    for(i=(n/2-1);i>=0;i--)        // n/2-1为最后一个非叶子结点下标
        Adjust(a,i,n);

    for(i=n-1;i>=1;i--){        //进行n-1次循环完成堆排序
        //堆顶(最大元素)与最后一个元素对换,最大元素换到数组末尾
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        Adjust(a,0,i-1);    //调整堆顶元素,使其再次成为大顶堆
    }
}

/*从大到小排序*/
void Adjust(int a[],int low,int high);
void HeapSort(int a[],int n);
//调整小顶堆
//数组从下标1开始存储数据,对下标为low的元素进行调整，右边界下标为high
void Adjust(int a[],int low,int right)
{
    int i = low,j = 2*i;    //a[j]为a[i]的左孩子
    temp = a[low];        //记录被调整结点的值
    while(j<=right){
        if(j<right&&a[j]>a[j+1])
            j++;            //令j指向较小的孩子
        //保证父结点小于孩子结点
        if(temp>a[j]){        
            a[i] = a[j];
            i = j;
            j = 2*i;
        }else
            break;
    }
    a[i] = temp;    //被调整结点的值放入最终位置
}

void HeapSort(int a[],int n)
{
    int i,temp;
    //建立小顶堆
    for(i=n/2;i>=1;i--)        // n/2为最后一个非叶子结点
        Adjust(a,i,n);

    for(i=n;i>=2;i--){
        //堆顶(最小元素)与最后一个元素对换,最小元素换到数组末尾
        temp = a[1];
        a[1] = a[i];
        a[i] = temp;
        Adjust(a,1,i-1);    //调整堆顶元素,使其再次成为小顶堆
    }
}

堆排序C/C++

推荐阅读