随感而发

杂七杂八

统计

留言簿(13)

阅读排行榜

评论排行榜

堆排序

本来还想写点思路的,词穷,不知道怎么组织,算了。只有贴源代码了。希望以后的我不要怪我哦!还可以看书嘛。书上讲的已经很清楚了哦。呵呵。
由于是学习,所以只写了最大堆,也没有怎么优化和详细的测试。哎,无奈的贴上源代码:
#include <stdio.h>
#include 
<stdlib.h>

//交换两个整数。注意一定要if判断是否两个相等,如果
//不相等才交换,如果相等也交换会出错的。a^a = 0
inline void Swap(int& a, int& b)
{
    
if (a != b)
    {
        a
^= b;
        b
^= a;
        a
^= b;
    }
}

//维持一个最大堆
int Heapify(int* npData, int nPos, int nLen)
{
    
int nMax = -1;                        //暂存最大值
    int nChild = nPos * 2;                //他的左孩子位置

    
while(nChild <= nLen)                //判断他是否有孩子
    {
        nMax 
= npData[nPos];            //是当前最大值为他

        
if (nMax < npData[nChild])        //与左孩子比较
        {
            nMax 
= npData[nChild];        //如果比左孩子小,就时最大值为左孩子
        }

        
//同理与右孩子比较,这里要注意,必须要保证有右孩子。
        if (nChild + 1 <= nLen && nMax < npData[nChild + 1])    
        {
            
++nChild;                    //赋值最大值的时候把孩子变为右孩子,方便最后的数据交换
            nMax = npData[nChild];

        }

        
if (nMax != npData[nPos])        //判断是否该节点比孩子都打,如果不大
        {
            Swap(npData[nPos], npData[nChild]);    
//与最大孩子交换数据
            nPos = nChild;                        //该节点位置变为交换孩子的位置
            nChild *= 2;                        //因为只有交换后才使不满足堆得性质。
        }
        
else                            //都最大了,满足堆得性质了。退出循环
        {
            
break;
        }
    }

    
return 1;                        //维持结束。
}

//建立一个堆
int BuildHeap(int* npData, int nLen)
{
    
//从nLen / 2最后一个有叶子的数据开始,逐一的插入堆,并维持堆得平衡。
    
//因为堆是一个完全二叉树,所以nlen/2+1- nLen之间肯定都是叶子。
    
//叶子还判断什么呢。只有一个数据,肯定满足堆得性质咯。
    for (int i = nLen / 2; i >= 1--i)
    {
        Heapify(npData, i, nLen);
    }

    
return 1;
}

//堆排序
int HeapSort(int* npData, int nLen)
{
    BuildHeap(npData, nLen);        
//建立一个堆。

    
while(nLen >= 1)                //逐一交和第一个元素交换数据到最后
    {                                //完成排序
        Swap(npData[nLen], npData[1]);
        
--nLen;
        Heapify(npData, 
1, nLen);//交换之后一定要维持一下堆得性质。
    }                            //不然小的成第一个元素,就不是堆了。

    
return 1;
}

//main函数,
int main()
{
    
int nData[11= {0,9,8,7,6,5,4,3,2,1,0};    //测试数据,下标从1开始哦。
    HeapSort(nData, 10);                        //堆排序

    
for (int i = 1; i <= 10++i)                //输出排序结果。
    {
        printf(
"%d ", nData[i]);
    }
    printf(
"\n");
     system(
"pause");
    
return 0;
}

呵呵,等知道怎么写思路了补上。。

posted on 2009-04-21 20:00 shongbee2 阅读(4196) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理