2.2 C语言_实现数据容器vector(排序功能)

nimeijian 2019-10-21

上一节我们说到我们己经实现了一般Vector可以做到的自动扩充,告诉随机存取,那么现在我们需要完成vector的一个排序的功能。

排序算法我们网上一百度哇~~!很常见的就有8大排序算法;

1.选择排序  2.冒泡排序  3.插入排序  4.快速排序

5.归并排序  6.桶排序  7.堆排序  8.希尔排序

具体的思想本猿就不展开讲啦,现在C语言应用的场景大多数在服务器和嵌入式设备,服务器数据量大,嵌入式设备资源有限

两者是对时间复杂度和空间负责度的两个极端。

一开始我想要优化堆排序,使得堆排序的空间复杂度减小;

优化的思想很简单;我们并不申请一个与原数组大小一致的空间,而是申请一个他的映射数组;

当我们堆排序 insert 和 delete 后,映射数组中就存储了有序数据的信息;

例如:映射数组mapTab[0] = 20; //也就意味着真正有序数组的第0位是现在数组的第20位;将第20位移动至第0位;在有序数组的第20位

现在在哪一个位置;依次跳转映射,将整个映射表遍历后,数组就变成有序的啦;

以下是实现代码:

/*
 *
 * 此函数为堆排序的改进版本,使用了一个数组作为数据的映射,使用此数组记住当前位置正确的数据下标是多少;
 * 例如 数组a[0] = 12;即表示 在真正有序的数据中第 [0] 位应该是现在的第12位数据;但是在这里为了节约空间,
 * 将数据的顺序颠倒;也就是说 a[maxsize] 中存放的数字下标就是有序数据的第[0]位;
 *
 * insert delete后,生成的数组就是我们的映射表,这个是依照迭代的思想,从第0位开始,找出第0位应该存放的数据是第n位,
 * 迭代,需要应该在第n位的数据现在在第y位。依次寻找迭代;
 * 由此一定会迭代出一个循环,此时将之前缓存起来的第0位数据放入它应该去的位置,同时,自增,查看第1位,如果第1位已经就绪则继续自增
 * 性能分析;
 * 此方法相对于堆排序,将空间缩减为每个元素只占用5个字节,如果元素类型大小小于5,则使用此方法将浪费空间和时间,
*/
void heapSortInt(VCT_DOU_t *v)
{
    u32 *mapTab = (u32 *)malloc(sizeof(u32) * (v->size + 1));
    //    u32 temp[50] = {0};
    u32 index = 0;
    // insert min
    for (u32 i = 1; i <= v->size; i++)
    {
        index = i;
        for (; index > 1 && v->compare(&v->data[i - 1], &v->data[mapTab[(index >> 1)]]); index >>= 1)
            mapTab[index] = mapTab[index >> 1];
        mapTab[index] = i - 1;
    }
    // delete min
    u32 child = 0;
    u32 minindex;
    for (u32 i = 0; i < v->size; i++)
    {
        minindex = mapTab[1];
        mapTab[1] = mapTab[v->size - i];
        index = 1;
        for (; (index << 1) <= (v->size - i - 1); index = child)
        {
            child = (index << 1);
            if (child != (v->size - i - 1) && compare(&v->data[mapTab[child + 1]], &v->data[mapTab[child]]))
            {
                child++;
            }
            if (compare(&v->data[mapTab[child]], &v->data[mapTab[v->size - i]]))
                mapTab[index] = mapTab[child];
            else
                break;
        }
        mapTab[index] = mapTab[v->size - i];
        mapTab[v->size - i] = minindex;
    }

    //    double t;
    u8 *sta = (u8 *)malloc(sizeof(u8) * v->size);
    //    u8 sta[50] = {0};
    template_t t = {0};
    memset(sta, 0, sizeof(u8) * v->size);
    for (u32 i = v->size; i > 0; i--)
    {
        printf("\n[%d]  %d", i, mapTab[i]);
        if (sta[v->size - i] == 1)
            continue;
        t = v->data[v->size - i];
        u32 start = v->size - i;
        u32 next = mapTab[i];
        while (next != (v->size - i))
        {
            v->data[start] = v->data[next];
            sta[start] = 1;
            start = next;
            next = mapTab[v->size - next];
        }
        v->data[start] = t;
        sta[start] = 1;
    }
    v->show(v);
}

经过本猿的测试发现,时间消耗是普通堆排序的5倍时间(数组大小10000000);虽然时间复杂度依旧是nlogn,但是我还是不能接受,奈何自己实在没有想到更好的优化方法;

不得已,只能转变策略;

我个人而言对快读排序不太放心,虽然它被广泛使用,但是其性能是不稳定的,而堆排序就很稳定,因此我在头文件中定义了一个宏。如果这个宏有配置使用快排或者堆排序,那么

就使用快排或者堆排序,否则就使用冒泡排序;

现已将代码上传至github:https://github.com/KimAlittleStar/cstd

目录

1.引言

2.1实现简单基础的vector

2.2实现排序功能的vector

相关推荐

whtqsq / 0评论 2019-06-21