将一个数字插入排序的数组！ [英] Inserting a number into a sorted array!

问题描述

我想编写一段代码，用于在适当的位置将一个数字插入排序的数组（即数组在插入后仍应保持排序）

我的数据结构不允许重复。

我打算这样做：

1. 找到正确的索引，我应该使用二进制搜索来放置这个元素


2. 通过将索引中的所有元素向下移动，为此元素创建空间。


3. 把这个元素放在那里。

还有其他更好的方法吗？

解决方案

如果你真的有一个数组，而不是一个更好的数据结构，那是最佳的。如果您对实施有灵活性，请查看 AA树木 - 他们相当快并易于实施。显然，比数组占用更多的空间，如果元素数量不足以注意到与指针魔法相比，blit的缓慢程度是不值得的。

I would like to write a piece of code for inserting a number into a sorted array at the appropriate position (i.e. the array should still remain sorted after insertion)

My data structure doesn't allow duplicates.

I am planning to do something like this:

1. Find the right index where I should be putting this element using binary search
2. Create space for this element, by moving all the elements from that index down.
3. Put this element there.

Is there any other better way?

解决方案

If you really have an array and not a better data structure, that's optimal. If you're flexible on the implementation, take a look at AA Trees - They're rather fast and easy to implement. Obviously, takes more space than array, and it's not worth it if the number of elements is not big enough to notice the slowness of the blit as compared to pointer magic.

这篇关于将一个数字插入排序的数组！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！