将项目插入排序列表 [英] Inserting an item into a sorted list
问题描述
我在一次采访中完全轰炸了这个问题所以我在这里发布我的答案
征求意见和建议......也许（上帝帮助我）我不是那样的/>
明亮，但这很有效，而且似乎相当高效。这个想法很简单，
在一个已经排序的列表中插入一个整数。
private int [] _list;
....
public void Insert（int value）
{
int [] tempArray;
//检查特殊情况
if（this._list == null）
{//第一项添加创建新阵列
this._list = new int [1];
this._list [0] = value;
return;
}
else if（this._list [this._list.Length-1]< = value）
{//要添加的项目大于最后一项
//数组中的项目，追加项目结束
tempArray = new int [this._list.Length + 1];
Array.Copy（this._list，tempArray，this._list.Length）;
this._list = tempArray;
this._list [this._list。长度-1] =值;
返回;
}
否则if（this._list [0]> =值）
{//要添加的项目小于数组中的第一个
//项目，插入项目开头
tempArray = new int [this._list.Length + 1];
Array.Copy（this._list，0，tempArray，1，this._list.Length）;
this._list = tempArray;
this ._list [0] =价值;
返回;
}
int left = 0;
int right = this._list.Length;
int middle = 0;
int mod = 0;
//二元搜索循环
while（left< = right）
{
//修改轴心点
middle =（left + right）/ 2;
if（value> this._list [middle]）
{//项目大于支点
//Debug.WriteLine（value +">" ; + this._list [middle]）;
mod = 1;
left = middle + 1;
}
else if（value< this._list [middle]）
{// item小于支点
// Debug。 WriteLine（值+"<" + this._list [middle]）;
mod = 0;
right = middle - 1; < br $>
}
其他
{//项目等于枢轴点
//调试.WriteLine（值+" =" + this._list [middle]）;
休息;
}
}
//再次修改轴心点
middle + = mod;
//重建数组以允许新的空间item
tempArray = new int [this._list.Length + 1];
Array.Copy（this._list，0，tempArray，0，middle）;
Array.Copy（this._list，middle，tempArray，middle + 1，te mpArray.Length -
（中间+1））;
//插入新项目
this._list = tempArray;
this._list [middle] = value;
}
I totally bombed this question in an interview so I''m posting my answer here
for comments and suggestions... perhaps (god help me) I''m just not that
bright, but this works and seems to be fairly efficent. The idea was simple,
insert an integer into a list that has already been sorted.
private int[] _list;
....
public void Insert(int value)
{
int[] tempArray;
// check for special cases
if (this._list == null)
{ // first item added create new array
this._list = new int[1];
this._list[0] = value;
return;
}
else if (this._list[this._list.Length-1] <= value)
{ // item to be added is greater than the last
// item in the array, append item to end
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, tempArray, this._list.Length);
this._list = tempArray;
this._list[this._list.Length-1] = value;
return;
}
else if (this._list[0] >= value)
{ // item to be added is less than the first
// item in the array, insert item to the beginning
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, 0, tempArray, 1, this._list.Length);
this._list = tempArray;
this._list[0] = value;
return;
}
int left = 0;
int right = this._list.Length;
int middle = 0;
int mod = 0;
// binary search loop
while (left <= right)
{
// modify the pivot point
middle = (left + right) / 2;
if (value > this._list[middle])
{ // item is greater than the pivot point
//Debug.WriteLine(value + " > " + this._list[middle]);
mod = 1;
left = middle + 1;
}
else if (value < this._list[middle])
{ // item is less than the pivot point
//Debug.WriteLine(value + " < " + this._list[middle]);
mod = 0;
right = middle - 1;
}
else
{ // item is equal to the pivot point
//Debug.WriteLine(value + " = " + this._list[middle]);
break;
}
}
// modify the pivot point again
middle += mod;
// rebuild array to allow space for new item
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, 0, tempArray, 0, middle);
Array.Copy(this._list, middle, tempArray, middle+1, tempArray.Length -
(middle +1));
// insert new item
this._list = tempArray;
this._list[middle] = value;
}
推荐答案
我没有仔细阅读过代码，但是我认为这可能会稍微提高性能（取决于Array.Copy如何实现
）。
最后，你有两个复制语句复制了
数组的每一半，留下了新数字的间隙。
一个建议（并且如果我过于强迫强迫我就原谅我）是
而不是两个，只需拨打一次电话就可以更有效率$ / b $ b Array.Copy到一个更大的数组。这样做会使最后的
元素保持不变。然后插入您的值作为最后一个元素，然后交换
最后一个元素与pivot值。如果Array.Copy是高效的，那么它将会执行内存复制，而不是枚举值（就像我说的那样，我不知道
我真的不知道实现）。
不知道它是否会做任何事情而只是一个想法。
Ryan Graham < RY **** @ earthlink.net>在留言中写道
news：kc ***************** @ newsread3.news.pas.earthl ink.net ...
I have not read the code too closely, but here is what I see that could
improve performance slightly (depending on how the Array.Copy is
implemented).
Toward the end, you have two copy statements which copy each half of the
array leaving a gap for the new number.
One suggestion (and forgive me if I am too obsessive compulsive) is that
rather then two, it might be more efficient to make just one call to
Array.Copy to an array that is one bigger. Doing this will leave the last
element undefined. Then insert your value as the last element, then swap
the last element with the pivot value. If Array.Copy was efficient, it
would do a memory copy rather then enumerating the values (like I said, I
don''t really know the implementation).
Don''t know if it would do anything but just a thought.
"Ryan Graham" <ry****@earthlink.net> wrote in message
news:kc*****************@newsread3.news.pas.earthl ink.net...
我在一次采访中完全轰炸了这个问题，所以我发布了我的答案
这里
征求意见和建议......也许（上帝帮助我）我只是不是那样的很明亮，但这很有效，而且似乎相当高效。这个想法很简单，
在一个已经排序的列表中插入一个整数。
private int [] _list;
...
public void Insert（int value）
{
int [] tempArray;
//检查特殊情况
if（this._list == null）
{//第一项添加创建新数组
this._list = new int [1];
this._list [0] = value;
return;
}
else if（this._list [this._list.Length-1]< = value）
{//要添加的项目大于上一个
//项目在数组中，追加项目结束
tempArray = new int [this._list.Length + 1];
Array.Copy（this._list，tempArray，this._list.Length） ;
this._list = tempArray;
this._list [this._list.Length-1] = value;
return;
}
else if（this._list [0]> = value）
{//要添加的项目少于第一个
//数组中的项目，将项目插入到开头
tempArray = new int [this._list.Length + 1];
Array.Copy（this._list，0，tempArray， 1，this._list.Length）;
this._list = tempArray;
this._list [0] = value;
return;
}
int left = 0;
int right = this._list.Length;
int middle = 0;
int mod = 0;
/ /二进制搜索循环
while（left< = right）
{
//修改轴心点
middle =（left + right）/ 2;
if（value> this._list [middle]）
{//项目大于枢轴点
//Debug.WriteLine(value +">" + this._list [middle] ）;
mod = 1;
left = middle + 1;
}
if if（value< this._list [middle]）
{// item小于枢轴点
//Debug.WriteLine（value +"<" + this._list [middle]）;
mod = 0;
right = middle - 1;
}
{//项目等于枢轴点
//Debug.WriteLine（value +" ; =" + this._list [middle]）;
break;
}
//再次修改轴心点
中间+ = mod;
//重建数组以允许新项目的空间
tempArray = new int [this._list.Length + 1];
Array.Copy（this._list ，0，tempArray，0，middle）;
Array.Copy （this._list，middle，tempArray，middle + 1，tempArray.Length -
（中间+1））;
//插入新项目
this._list = tempArray ;
this._list [middle] = value;
}
I totally bombed this question in an interview so I''m posting my answer
here
for comments and suggestions... perhaps (god help me) I''m just not that
bright, but this works and seems to be fairly efficent. The idea was
simple,
insert an integer into a list that has already been sorted.
private int[] _list;
...
public void Insert(int value)
{
int[] tempArray;
// check for special cases
if (this._list == null)
{ // first item added create new array
this._list = new int[1];
this._list[0] = value;
return;
}
else if (this._list[this._list.Length-1] <= value)
{ // item to be added is greater than the last
// item in the array, append item to end
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, tempArray, this._list.Length);
this._list = tempArray;
this._list[this._list.Length-1] = value;
return;
}
else if (this._list[0] >= value)
{ // item to be added is less than the first
// item in the array, insert item to the beginning
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, 0, tempArray, 1, this._list.Length);
this._list = tempArray;
this._list[0] = value;
return;
}
int left = 0;
int right = this._list.Length;
int middle = 0;
int mod = 0;
// binary search loop
while (left <= right)
{
// modify the pivot point
middle = (left + right) / 2;
if (value > this._list[middle])
{ // item is greater than the pivot point
//Debug.WriteLine(value + " > " + this._list[middle]);
mod = 1;
left = middle + 1;
}
else if (value < this._list[middle])
{ // item is less than the pivot point
//Debug.WriteLine(value + " < " + this._list[middle]);
mod = 0;
right = middle - 1;
}
else
{ // item is equal to the pivot point
//Debug.WriteLine(value + " = " + this._list[middle]);
break;
}
}
// modify the pivot point again
middle += mod;
// rebuild array to allow space for new item
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, 0, tempArray, 0, middle);
Array.Copy(this._list, middle, tempArray, middle+1, tempArray.Length -
(middle +1));
// insert new item
this._list = tempArray;
this._list[middle] = value;
}
这是一个非常简单的版本。还有一些评论：
*数组类包含一个静态二进制搜索方法。
*首先需要特殊情况，最后一项。 Just Array.Copy零项
*除非由于某种原因需要空数组，否则更容易只需要
使私有数组在初始化时为零长度。那样就没有需要在操作它的所有方法中使用空值检查。
private int [] array = new int [0];
public void Insert（int value）
{
int [] newArray = new int [array.Length + 1];
//数组已排序，因此我们可以使用二进制搜索来查找插入点
int spot = Array.BinarySearch（array，value）;
//如果找不到值，则将spot设置为下一个
//更高值'的索引的负数。
if（spot< ; 0）
spot = -spot - 1; //在较大的项目之前将插入点设置为索引。
Array.Copy（array，newArray，spot）;
newArray [spot] = value;
Array.Copy（array，spot，newArray，spot + 1，array.Length - spot）;
array = newArray;
}
-
MarcusAndrén
Here is a quite simple version. And a few comments:
* Array class contains a static binary search method.
* No need to special case first, last item. Just Array.Copy zero items
* Unless null array is needed for some reason it is easier to just
make the private array zero length at initalization. That way there is
no need to employ null checks in all methods manipulating it.
private int[] array = new int[0];
public void Insert(int value)
{
int[] newArray = new int[array.Length+1];
//Array is sorted so we can use binary search to find insert spot
int spot = Array.BinarySearch(array, value);
//If value is not found, spot is set to the negative of the next
//higher value''s index.
if (spot < 0)
spot = -spot - 1; //Set insert spot to index before larger item.
Array.Copy(array, newArray, spot);
newArray[spot] = value;
Array.Copy(array, spot,newArray, spot+1,array.Length - spot);
array = newArray;
}
--
Marcus Andrén
我很感激输入，只是为了澄清意图是练习我自己的
二元搜索算法。
"MarcusAndrén" < a@b.c>在留言中写道
news：3k ******************************** @ 4ax.com ...
I appreciate the input, just to clarify the intent was to practice my own
binary search algorithm.
"Marcus Andrén" <a@b.c> wrote in message
news:3k********************************@4ax.com...
这是一个非常简单的版本。还有一些评论：
*数组类包含静态二进制搜索方法。
*首先需要特殊情况，最后一项。 Just Array.Copy零项目
*除非由于某种原因需要空数组，否则更容易使私有数组在初始化时保持零长度。这样就没有必要在操作它的所有方法中使用空值检查。
private int [] array = new int [0];
public void Insert（int value）
{
int [] newArray = new int [array.Length + 1];
//数组已排序，因此我们可以使用二进制搜索来查找insert spot
int spot = Array.BinarySearch（array，value）;
//如果找不到值，则spot设置为下一个
//更高值的负数index。
if（spot< 0）
spot = -spot - 1; //在较大的项目之前将插入点设置为索引。
Array.Copy（array，newArray，spot）;
newArray [spot] = value;
Array.Copy（array ，spot，newArray，spot + 1，array.Length - spot）;
array = newArray;
}
- MarcusAndrén
Here is a quite simple version. And a few comments:
* Array class contains a static binary search method.
* No need to special case first, last item. Just Array.Copy zero items
* Unless null array is needed for some reason it is easier to just
make the private array zero length at initalization. That way there is
no need to employ null checks in all methods manipulating it.
private int[] array = new int[0];
public void Insert(int value)
{
int[] newArray = new int[array.Length+1];
//Array is sorted so we can use binary search to find insert spot
int spot = Array.BinarySearch(array, value);
//If value is not found, spot is set to the negative of the next
//higher value''s index.
if (spot < 0)
spot = -spot - 1; //Set insert spot to index before larger item.
Array.Copy(array, newArray, spot);
newArray[spot] = value;
Array.Copy(array, spot,newArray, spot+1,array.Length - spot);
array = newArray;
}
--
Marcus Andrén
这篇关于将项目插入排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
