`
中国小虫
  • 浏览: 12515 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

排序------堆排序

    博客分类:
  • C
c 
阅读更多
先把代码贴上来先,网友们如果发现有啥错误,直说哈。至于原理,会跟另一个版本的一起贴上来。
/*-------exchange---------- 
函数名 :exchange;
功能   : 进行两个的交换;
参数   : 进行比较的两个数的指针;
返回值 : 为空; 
 -------------------------*/
void exchange(int *a, int *b)   
{   
    int t;   
    t = *a;   
    *a = *b;   
    *b = t;   
}   
  
/*-------part_sort---------- 
函数名 :part_sort;
功能   : 对无序区进行一次堆排序---相当于建堆;
参数   : 无序区的长度int n, 待排序的数组int *a;
返回值 : 为空; 
-------------------------*/    
int part_sort(int n, int *a)  //进行一次堆排序   
{   
    int temp, t, i;   
       
    for( i = n / 2; i >= 1; i--)   
    {   
        temp = 2 * i;   
        if(temp <= (n-1) && a[temp] < a[temp+1])   
        {   
            temp++;   
        }   
  
        if(a[i] < a[temp])   
        {   
            exchange(&a[i], &a[temp]);   
        }   
    }   
}   
/*-------heapsort----------
函数名 :heapsort;
功能   : 堆排序的主体函数,实现排序,进行递归;
参数   : 待排序的数组int *a, 无序区的长度 int n;
返回值 : 整型int ; 
-------------------------*/
int heapsort(int *a, int n)  //  n 并非 数组的总长度, 是无序区的长度;<BR>{   
    int temp;   
  
    if(n == 1)   
    {   
        return 0;   
    }   
  
    part_sort(n, a);  // 对a[1]....a[n].进行一次堆排序;   
  
    exchange(&a[1] , &a[n]);    //将堆顶a[1] 与 无序区的 最后一个元素 也就是a[n]进行交换    
  
    heapsort(a, n-1);//将 a[n] 归入有序区, 无序区变为a[1].......a[n-1].进行递归;   
  
    return 1;   
  
} 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics