c – 将排序插入到小(255个元素)列表中

发布时间：2020-12-16 04:51:23 所属栏目：百科来源：网络整理

导读：我正在寻找一个合适的算法来构建一个相对较小(最多255个元素)排序的整数数组.目标平台是基于STM32的嵌入式系统.由于存储器是有限的,因此优选就地方法. 我知道显而易见的方法是实现和描述通常的嫌疑人(快速排序,插入sert,shell排序),但是想要问你的经历.更具

我正在寻找一个合适的算法来构建一个相对较小(最多255个元素)排序的整数数组.目标平台是基于STM32的嵌入式系统.由于存储器是有限的,因此优选就地方法.

我知道显而易见的方法是实现和描述通常的嫌疑人(快速排序,插入sert,shell排序),但是想要问你的经历.更具体地说,在构建阵列时,我发现很少有关于性能的信息 – 也就是说,不同的算法可以使用所有现有元素已经订购的事实.

编辑1：
虽然问题标记为C,但STL不可用.此外,排序确实发生在内循环内.为了进一步说明,我正在寻找一种特别适合以有效方式构建排序列表的算法.我假设(可能是错误的)必须有专门适合这项任务的算法.这就是问题所在.

编辑2：
当说构建排序列表时,我的意思是列表开始为空并且由16位整数的有界数字(最多255个)填充,这些数字没有特定的顺序.必须在存储所有元素后处理该列表.对于处理,必须对列表进行排序,优选地按降序排序.

提前致谢,
阿恩

解决方法

如果您的问题要求：

>您将元素完全排序在实际的C/C++数组中,并且
>您始终按排序顺序维护项目,

然后你把自己画成一个角落：你的要求拼写“插入排序”.

无论您选择何种算法或辅助数据结构,在中间插入一个新元素都需要您通过索引向上移动较大的元素,并删除任何元素(最大的元素除外)将要求您将较大的元素向下移动指数.由于插入排序正是如此,没有任何额外的逻辑或数据结构,您也可以使用它.

唯一的例外是如果您的比较特别昂贵.如果是这种情况,那么您可以使用binary search来查找插入点(而不是在移动时将新元素与每个旧元素进行比较).但是,您仍然需要移动大于突变点的所有元素,因此您永远无法提高O(N)之后的性能(尽管批??量数据移动应该非常快……).

此外,您应该评估您的要求：如果您知道N< 256,在0位置插入一个对象的最坏情况对你的应用来说足够快,你应该停在那里.为了节省你不需要的时间,让事情变得比必要的更复杂是没有意义的. 另一方面,如果：
>您实际上并不需要始终对所有元素进行完全分类,并且
>您实际需要的是重复查找和删除数组中最大/最小的元素

那么你所需要的是一个priority queue,你可以使用implicit heap实现它(以内存效率,就地方式).隐式堆操作是O(log N),通常具有良好的性能因素;即使N = 255,这也会对最坏情况下的性能产生很大影响.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!