开发者社区> 问答> 正文

计算机二级的中的“堆排序法”是怎么排的?

计算机二级的中的“堆排序法”是怎么排的?

展开
收起
知与谁同 2018-07-22 09:12:31 2813 0
1 条回答
写回答
取消 提交回答
  • 胜天半子
    堆排序法,就是通过堆这种数据结构来实现排序,算法复杂度为O(nlogn)。
    堆是一种完全二叉树且所有的父节点均大于(或小于)其子节点。
    堆排序就是将所有待排序的元素组成一个堆,然后不断弹出堆顶的元素并调用函数维持堆序,直到所有元素均被弹出后,排序完成。被弹出的元素序列即一个有序数列。

    维持堆序的一般做法是这样:

    当一个节点被插入时,将该节点放在堆的末尾(这是为了保证堆是完全二叉树)然后将该节点与它的父节点比较,看该节点是否大于(或小于)其父节点,即判断当前的堆是否满足堆序。如果不满足,则将该节点与其父节点交换。再将该节点与其新的父节点做比较,依此类推,直到该节点不再需要与其父节点交换为止。(即满足堆序时停止)

    当一个根节点被弹出(即被从堆中删除)时,将堆最尾部的节点移动到头结点的位置,然后将该节点不断与其子节点比较,如果不符合堆序则交换,直到符合堆序为止。

    以下是我自己写的一个C++的堆排序的程序,希望对你理解该算法有帮助。

    #include<iostream>
    using namespace std;
    int heap[10000],size;
    void Percup(int s)
    {
    if(s==1)
    return ;
    if(heap[s/2]<heap[s])
    {
    swap(heap[s/2],heap[s]);
    Percup(s/2);
    }
    }
    void Percdown(int s)
    {
    if(s*2+1<=size&&heap[s*2+1]>heap[s])
    {
    swap(heap[s*2+1],heap[s]);
    Percdown(s*2+1);
    }
    if(s*2<=size&&heap[s*2]>heap[s])
    {
    swap(heap[s*2],heap[s]);
    Percdown(s*2);
    }
    }
    void Insert(int k)
    {
    heap[++size]=k;
    Percup(size);
    }
    int Pop()
    {
    int h=heap[1];
    heap[1]=heap[size--];
    Percdown(1);
    return h;
    }
    int main()
    {
    int a,n,i;
    cin>>n;
    for(i=0;i<n;i++)
    {
    cin>>a;
    Insert(a);
    }
    for(i=0;i<n;i++)
    cout<<Pop()<<' ';
    system("pause");
    return 0;
    }
    2019-07-17 22:50:24
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载