• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C++简单交换堆排序

OC/C/C++ 水墨上仙 1428次浏览

C++简单交换堆排序

/* Can easily be modified to work with other data types */
 
void heapsort(int *arr, int n)
{
    int start, end;
 
    // heapify the array
    for(start = (n - 2) / 2; start >= 0; --start) // for every root
        siftDown(arr, start, n); // sift through it
     
    // sort the array
    for(end = n - 1; end; --end) // for every element of the heap
    {
        swapi(&arr[end], &arr[0]); // swap it with the top root
        siftDown(arr, 0, end); // rebuild the heap
    }
}
 
void siftDown(int *arr, int start, int end)
{
    int root, child;
 
    root = start; // pick the root index
    while(2 * root + 1 < end) // while the root has a child
    {
        child = 2 * root + 1; // pick its index
        if((child + 1 < end) && (arr[child] < arr[child+1]))
            ++child; // if the other child is bigger, pick it instead
        if(arr[root] < arr[child]) // if root is smaller than the child
        {
            swapi(&arr[child], &arr[root]); // swap them
            root = child; // go down the heap
        }
        else // if the child is smaller than the root
            return; // that root is in the right spot
    }
}
 
void swapi(int *x, int *y)
{
    int z;
     
    z = *x;
    *x = *y;
    *y = z;
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C++简单交换堆排序
喜欢 (0)
加载中……