堆排序的思路与改进(C 语言描述)

in 网站建设
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

本文中的代码适用于对数组元素进行排序(以整型数据为例)。

关于堆排序的具体思路可以参考《算法》书中描述 堆排序

自定义的方法

在排序方法之前,定义了五个不同的方法,以便于对数组元素进行比较、交换和覆盖。为了适用于不同的数据类型,这里使用到了 void 指针以及指针类型的转换,也就是 C 语言中范型的概念。如果需要对不同元素类型的数组进行排序,只修改 LessArr() 方法即可。

// 比较数组中两个元素大小的方法
int LessArr(void *arr, int i, int j, int size)
{
    return *(int*) (arr + (i - 1) * size) < *(int*) (arr + (j - 1) * size);
}

// 交换数组中两个元素的方法
void Exch(void *arr, int i, int j, int size)
{
    void * temp = malloc(size);
    memcpy(temp, arr + (i - 1) * size, size);
    memcpy(arr + (i - 1) * size, arr + (j - 1) * size, size);
    memcpy(arr + (j - 1) * size, temp, size);
    free(temp);
}

// 实现数组中元素的覆盖
void Cover(void * arr, int i, int j, int size)
{
    memcpy(arr + (i - 1) * size, arr + (j - 1) * size, size);
}

// 数组中元素的下沉方法
void Sink(void *arr, int k, int n, int size)
{
    while (2 * k <= n)
    {
        int j = 2 * k;
        if (j < n && LessArr(arr, j, j + 1, size)) ++j;
        if (!LessArr(arr, k, j, size)) break;
        Exch(arr, k, j, size);
        k = j;
    }
}

// 数组中元素的上浮方法
void Swim(void *arr, int k, int size)
{
    while (k > 1 && LessArr(arr, k / 2, k, size))
    {
        Exch(arr, k, k / 2, size);
        k /= 2;
    }
}

未改进的堆排序(下沉排序)

相比于其他比较或交换类的方法,堆排序的思路不同,它利用了二叉堆的性质,对数组实现原地排序。是一种不稳定的排序算法,这里我们介绍两种思路,一种是基本的下沉排序,另一种是 Floyd 提出的改进策略。

// 基本堆排序的方法
void HeapSort_Basic(void *arr, int n, int size)
{
    for (int k = n / 2; k != 0; --k)
        Sink(arr, k, n, size);
    // 这里如此修改的目的是为了避免一次多余的 Sink
    // 如想简化代码可以将下面 Exch() 一行删掉,再将 while 循环内的两行代码互换
    Exch(arr, 1, n--, size);
    while (n != 1)
    {
        Sink(arr, 1, n, size);
        Exch(arr, 1, n--, size);
    }
}

Floyd 改进策略(先下沉后上浮)

因为大多数重新插入堆的元素会直接加入到堆底,Floyd 发现我们可以免去检查元素是否到达正确位置来节省时间。也就是直接提升较大的子结点直至到达堆底,然后再使元素上浮

关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看