【数据结构】将一组数据升序排序（利用堆排序）-创新互联

堆排序相对冒泡排序、选择排序效率很高，不再是O（n^2）.

创新互联主要从事做网站、成都网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务铁锋,10多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220

假若将一个序列升序排序好，那么我们来考虑大堆还是最小堆来排序。假若是最小堆的话，堆的顶端必定是堆中的最小值，这样貌似可以。但是，如果是它的（一边或）子树左子树的节点数据值大于（一边或）右子树的节点数据值，直接打印肯定是错误的，而且对于此时的堆我们也无法操控来调整好正确的顺序了。

那我们换成大堆来实现升序想，当我们把序列调整成为大堆后，大堆顶端的数据值是大的，然后我们将这个大值与堆的最后一个叶子节点值来进行交换，再将交换后的顶端值进行调整，换到合适的位置处……重复这样的工作，注意：进行第2次交换就要将顶端元素值与倒数第2个节点元素值交换了，且调整顶端元素位置也不能一直调整到size-1处。（因为：size-1处的值已经是大）

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<assert.h>


void AdjustDown(int* a,int parent, int size)
{
    int child = 2 * parent + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child] < a[child + 1])
        {
            ++child;
        }
        if (a[child]>a[parent])
        {
            swap(a[child], a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}


void Print(int*a, int size)
{
    cout << "升序序列为："<<endl;
    for (int i = 0; i < size; i++)
    {
        cout << a[i] << "  ";
    }
    cout << endl;
}


void HeapSort(int* a,int size)
{
    assert(a);
    
    //建成大堆
    for (int i = (size - 2) / 2; i >=0; i--)
    {
        AdjustDown(a,i, size);
    }

    //交换顺序
    for (int i = 0; i < size; i++)
    {
        swap(a[0], a[size - i - 1]);
        AdjustDown(a, 0, size-i-1);
    }    
}

 
void Test()
{
    int arr[] = { 12, 2, 10, 4, 6, 8, 54, 67,100,34,678, 25, 178 };
    int size = sizeof(arr) / sizeof(arr[0]);
    HeapSort(arr, size);    
    Print(arr,size);
}


int main()
{
    Test();
    system("pause");
    return 0;
}

时间复杂度：

（n-2）/2*lgn+n*(1+lgn)--->O(n).

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

新闻标题：【数据结构】将一组数据升序排序（利用堆排序）-创新互联
文章源于：https://www.cdcxhl.com/article40/codceo.html

成都网站建设公司_创新互联，为您提供云服务器、电子商务、企业网站制作、自适应网站、网站策划、网站制作

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联