有没有一种更好的方法将元素添加到排序位置的数组中？

Question

这个方法只是获取一个元素，并将其插入到已经排序的数组中的排序位置。

@ary = [9,7,3,1]
insert_in_order(5)
@ary = [9,7,5,3,1]

我已经确定这比仅仅在数组上压入值并运行排序要快！待会再说。但看起来这比它应该采取的步骤要多得多。有没有一种更高效、更高效的方法来做到这一点？

def insert_in_order val
    @val = val
    @ary.each_with_index{|v,i| 
        if @val > v
            @found_index = i 
            break
        end
        }
    @found_index ? @ary.insert(@found_index, @val) : @ary.push(@val)
end

Answer 1

执行二进制搜索并找到此元素所属的索引，然后在该索引处插入。查找索引需要O(log(n))，并且只有在保证对当前列表进行排序的情况下才有效

Answer 2

即使使用二进制搜索，正如@Adithya Surampudi建议的那样，这也将是相当慢的。由于根据定义，数组的元素位于连续的内存位置，因此在最后第i个位置插入数组时，需要将i个元素向右移动一个位置，以便为新元素腾出空间。您可能想要考虑一种不同的数据结构，比如红黑树(如果您觉得幸运的话，也可以考虑常规的二进制搜索树)。

Answer 3

它的性能并不比你现在拥有的更好，但我认为它读起来很好，这比性能更重要，直到你确定你的应用程序中有一个瓶颈：

>> ary = [9,7,3,1] #=> [9, 7, 3, 1]
>> val = 5 #=> 5
>> bigger, smaller = ary.partition{|x| x >= val} #=> [[9, 7], [3, 1]]
>> [*bigger, val, *smaller] #=> [9, 7, 5, 3, 1]