堆排序

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void max_heap(int arr[],int start,int end)
{
    int dad=start;
    int son=dad*2+1;
    while(son<=end)///限定不超出调整区间
    {
        if(son+1<=end&&arr[son]<arr[son+1])
            son++;///选那个大的儿子与父亲节点判断
        if(arr[dad]>arr[son])
            return;
        else
        {
            swap(arr[dad],arr[son]);
            dad=son;
            son=dad*2+1;
        }
    }
}

void heap_sort(int arr[],int len)
{
    ///初始化最初的一个大根堆,从后向前依次调整
    for(int i=len/2-1;i>=0;i--)
    {
        max_heap(arr,i,len-1);
    }
    for(int i=len-1;i>0;i--)
    {
        ///每次将根顶与底交换,然后从头调整
        swap(arr[0],arr[i]);
        max_heap(arr,0,i-1);
    }
}
///时间:nlog(n)
int main()
{
    ///从小到大排用大根堆,反之用小根堆
    int arr[]={ 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len=(int)sizeof(arr)/sizeof(*arr);///排序区间长度
    heap_sort(arr,len);
    ///输出
    for(int i=0;i<len;i++)
        cout<<arr[i]<<endl;
    return 0;
}

参考:图解排序算法(三)之堆排序
堆排序- 维基百科

发表评论

电子邮件地址不会被公开。 必填项已用*标注