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

上一节我们说到我们己经实现了一般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