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.引言