Arn*_*rne 7 c c++ sorting algorithm
我正在寻找一个合适的算法来构建一个相对较小(最多255个元素)排序的整数数组.目标平台是基于STM32的嵌入式系统.由于存储器是有限的,因此优选就地方法.
我知道显而易见的方法是实现和描述通常的嫌疑人(快速排序,插入sert,shell排序),但是想要问你的经历.更具体地说,我在构建阵列时发现很少有关于性能的信息- 也就是说,不同算法可以使用所有现有元素已经订购的事实.
编辑1: 虽然问题标记为C++,但STL不可用.此外,排序确实发生在内循环内.为了进一步说明,我正在寻找一种特别适合以有效方式构建排序列表的算法.我假设(可能是错误的)必须有专门适合这项任务的算法.这就是问题所在.
编辑2: 当说构建排序列表时,我的意思是列表开始为空,并由16位整数的有界数字(最多255)填充,这些数字没有特定的顺序.必须在存储所有元素后处理该列表.对于处理,必须对列表进行排序,优选地按降序排序.
谢谢,Arne
如果您的问题要求:
然后你把自己画成一个角落:你的要求拼写"插入排序".
无论您选择何种算法或辅助数据结构,在中间插入一个新元素都需要您通过索引向上移动较大的元素,并删除任何元素(最大的元素除外)将要求您将较大的元素向下移动指数.由于插入排序正是如此,没有任何额外的逻辑或数据结构,您也可以使用它.
唯一的例外是你的比较特别贵.如果是这种情况,那么您可以使用二进制搜索来查找插入点(而不是在移动时将新元素与每个旧元素进行比较).但是,您仍然需要移动大于突变点的所有元素,因此您将永远无法提高O(N)之后的性能(尽管批量数据移动应该非常快......).
此外,您应该评估您的要求:如果您知道这一点N < 256,并且将对象插入到位的最坏情况0对于您的应用来说足够快,您应该停在那里.为了节省你不需要的时间,使事情变得比必要的更复杂是没有意义的.
另一方面,如果:
然后你需要的是一个优先级队列,你可以通过使用隐式堆来实现它(以内存效率,就地方式).隐式堆操作是O(log N),通常具有良好的性能因子; 即便如此N = 255,这可以在最坏情况下表现出很大的不同.