我知道显而易见的方法是实现和描述通常的嫌疑人(快速排序,插入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,这也会对最坏情况下的性能产生很大影响.
