• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

收藏的堆排序c++代码

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
//来自http://www.blogjava.net/dreamingnest/archive/2008/10/06/232668.html
#include<iostream>
#include<algorithm>
using namespace std;
int A[11],heap_size;
void MaxHeapify(int A[],int i)
{
    int largest=-1;
    int left=2*i;//获取根节点的左孩子
    int right=2*i+1;//获取根节点的右孩子
    if(left<=heap_size&&A[left]>A[i])
        largest=left;
    else
        largest=i;
    if(right<=heap_size&&A[right]>A[largest])
        largest=right;
    if(largest!=i)//根节点不是最大值则交换后继续递归
    {
        swap(A[i],A[largest]);
        MaxHeapify(A,largest);
    }
}
void BuildMaxHeap(int A[])
{
    for(int i=10/2;i>=1;i--)
        MaxHeapify(A,i);
}
int main()
{
    int i;
    heap_size=10;
    for(i=1;i<11;i++)
        cin>>A[i];
    BuildMaxHeap(A);
    cout<<"建立的最大堆为:";
    for(i=1;i<11;i++)
        cout<<A[i]<<"-";
    cout<<endl;
    for(i=10;i>1;i--)
    {
        swap(A[i],A[1]);
        heap_size--;
        MaxHeapify(A,1);
    }
    cout<<"排序后的结果为:";
    for(i=1;i<11;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    return 0;
}
//来自http://blog.csdn.net/Tuzki/archive/2008/10/08/3032175.aspx

#include <iostream>

#include <ctime>

using namespace std;

 

// 注意父子的计算方式。节点编号从0开始。

inline int parent(const int x) { return ((x-1)/2); }

inline int left(const int x) { return (2*x+1); }

inline int right(const int x) { return (2*x+2); }

 

int cmp = 0;    // 总共执行比较操作的次数

int swp = 0;    // 总共执行交换操作的次数

 

// 调整以i为根的子树,使之成为最大堆,size为堆的大小

void maxHeapify(int a[], int size, int i)

{

    cmp +=2;

    swp++;

 

    int l = left(i);

    int r = right(i);

    int largest = i;    // 最大堆的根

   

    if( (l < size) && (a[l] > a[i]) )        largest = l;

    if( (r < size) && (a[r] > a[largest]) )  largest = r;

    if( largest != i )

    {

        swap(a[i], a[largest]);         // 三个节点中较大者成为根

        maxHeapify(a, size, largest);   // 可能破坏了堆性质,重新调整

    }

}

 

void buildMaxHeap(int a[], int size)    // 建堆

{

    for(int i = (size-1)/2; i>=0; i--)

    {

        maxHeapify(a, size, i);

    }

}

 

void heapSort(int a[], int size)        // 堆排序,(n-1)*O(lgn) = O(nlgn)

{

    swp++;

 

    buildMaxHeap(a, size);

    for(int i=size-1; i>0; i--)         // 重复n-1

    {

        swap(a[0], a[i]);

        size--;

        maxHeapify(a, size, 0);         // 每次调整,花费为O(lgn)

    }

}

 

int main()

{

    int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

 

    heapSort(a, sizeof(a)/sizeof(a[0]));

 

    cout << "总共进行比较 " << cmp << " 次,总共进行交换 " << swp << " " << endl;

 

    for(int i=0; i<sizeof(a)/sizeof(a[0]); i++)

    {

        cout << a[i] << " ";

    }

    cout << endl;

 

    return 0;

}



鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#DataSet和DataTable详解发布时间:2022-07-14
下一篇:
C语言实现哈夫曼编码(最小堆,二叉树)发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap