堆排序算法的c/C++语言实现第二部

返回顶部
查看留言
转到底部

现在的位置: 首页 > 综合 > 正文

堆排序算法的c/C++语言实现第二部

2013年12月07日 ⁄ 综合 ⁄ 共 773字 ⁄ 字号小中大 ⁄ 评论关闭

#include <stdio.h>
/*
  Name: 
  Copyright: 
  Author: @dujianjian
  Date: 15/11/12 22:48
  Description: 大顶堆 
*/

//调整堆，使得元素满足堆的性质
void MAX_HEAPIFY(int a[],int i,int n){
      int left  = 2*i+1;
      int right = left +1;
      int largest;
      if(left <n-1){
    
       if( a[left]>a[right])      largest = left;
       else    largest = right ;    }    
     
   
   while(largest<n){
     if(a[i]>=a[largest])return;
     if(largest != i) {
                int temp   = a[i];
                a[i]       = a[largest];
                a[largest] = temp;              
                }
     MAX_HEAPIFY(a,largest,n);
      }      
     }

 //建堆，从数组的中间开始，逐个的调整，一直到根    
void BUID_MAX_HEAP(int a[],int n){
     for(int i =n/2-1;i>=0;i--)
       MAX_HEAPIFY(a,i,n);
     }

//堆排序，每次都把堆顶元素放到数组的尾部     
void HEAPSORT(int a[],int n){
     for(int i = n-1;i>=0;i--)
     {          int temp   = a[i];
                a[i]       = a[0];
                
                a[0] = temp;
                //n--;
                MAX_HEAPIFY(a,0,i);
                }
     }

//主函数，调用堆排序算法对数组进行排序，输出结果  
int main(){
    int a[10]={4,1,3,2,16,9,10,14,8,7};
    BUID_MAX_HEAP(a,10);
    HEAPSORT(a,10);
    for(int i=0;i<10;i++)
    printf("%d ",a[i]);
    getchar();
    return(0);
    }