java - 排序 vector - AddItem

Question

我已经编写了一个可以完全工作的排序 vector 。但是我的Add方法很长，我觉得有很多冗余代码。

我编写了一个二进制搜索函数，我想在我的 Add 方法中使用它，而不是在 Add 函数中也进行比较。

下面是我的代码:

public class SortedVector
{

  private int  maxcap = 10, noOfItems = 0, grow = 10;
  private String[] data = new String[maxcap];

  // Default Constructor
  public SortedVector()
  { 
  }

  public void SetGrowBy(int growby)
  {
      grow = growby;
  }


  public int GetCapacity()
  {
    return maxcap;
  }

  public int GetNoOfItems()
  {
    return noOfItems;
  }

  public String GetItemByIndex(int index)
  {

    if (index > noOfItems+1 || index < 0)
    {
      return null;
    }
    else
    {
      String item = data[index];
      return item;
    }
  }



  public int FindItem(String search)
  {
      int low=0;
      int high = noOfItems - 1; 

      return binarySearch(search, low, high);
  }


  public int binarySearch(String search, int low, int high)
  {
      if(low>high)
          return -1;
      int mid = (low + high)/2;
      if (data[mid] == search)
          return mid;
      else 
          if (data[mid].compareToIgnoreCase(search)<0)
              return binarySearch(search, mid+1, high);
          else
              return  binarySearch(search, low, mid-1);
  }



  public void AddItem(String value)
  {
      int thirdCounter = 0;
      int fourthCounter = 0;
      int place3= 0;
      int place4 =0;
      if(maxcap > noOfItems)
      {
          if(noOfItems == 0) 
          {
            data[0] = value;
            noOfItems++;
          }
          else
          {
            int firstCounter = noOfItems;
            for (int i=0; i < firstCounter; i++)
            {
               String[]temp = new String[maxcap]; 

               if(thirdCounter == 0)
               {
                if (data[i].compareToIgnoreCase(value)>0)
                {
                  for (int j=0; j < noOfItems; j++)
                  {
                     temp[j+1] = data[j]; 
                  }
                  data=temp;
                  data[0] = value;
                  noOfItems++;
                  thirdCounter++;
                }  
                else
                {
                    if(data[i].compareToIgnoreCase(value)<0)
                        {
                            for (int j=0; j < noOfItems; j++)
                            {
                               if (data[j].compareToIgnoreCase(value)>0)
                                {
                                    if(fourthCounter ==0)
                                    {
                                        temp[j+1] = data[j];
                                        place3 = j;
                                        fourthCounter++;
                                    }
                                   else
                                    {
                                        temp[j+1] = data[j];                                       
                                    }
                                }
                                else
                                {
                                    temp[j]=data[j];
                                    place4 = j;
                                }
                            }
                           if (place3 == 0)
                            {
                               if(place4 == 0)
                               {
                                data=temp;
                                data[1] = value;
                                noOfItems++;
                                firstCounter++;
                               }
                               else
                               {
                                data=temp;
                                data[place4+1] = value;
                                noOfItems++;
                                thirdCounter++;
                               }
                            }
                            else
                            {
                                data=temp;
                                data[place3] = value;
                                noOfItems++;
                                thirdCounter++;
                            }
                        }
                    }
               }
            }
          }
      }
      else
      {
            int firstCounter = 0;
            maxcap = grow +maxcap;
            String[]temp3 = new String[maxcap]; 
            for (int i=0; i < noOfItems; i++) 
             {
                 if(firstCounter == 0)
                 {
                    if (data[i].compareToIgnoreCase(value)>0) 
                    {
                     for (int j=0; j < noOfItems; j++)
                     {
                         temp3[j+1] = data[j];
                     }
                     data=temp3;
                     data[0] = value;
                     noOfItems++;
                     firstCounter++;
                    }
                    else
                    {  
                        int place1 = 0;
                        int place2 = 0;
                        int secondCounter = 0;
                        if(data[i].compareToIgnoreCase(value)<0)
                        {
                            for (int j=0; j < noOfItems; j++)
                            {
                                if (data[j].compareToIgnoreCase(value)>0)
                                {
                                    if(j/2!=0 && secondCounter ==0)
                                    {
                                        temp3[j+1] = data[j];
                                        place1 = j;
                                        secondCounter++;
                                    }
                                   else
                                    {
                                        temp3[j+1] = data[j];                                        
                                    }
                                }
                                else
                                {
                                    temp3[j]=data[j];
                                    place2 = j;
                                }

                            }
                            if (place1 == 0)
                            {
                               if(place2 == 0)
                               {
                                    data=temp3;
                                    data[1] = value;
                                    noOfItems++;
                                    firstCounter++;
                               }
                               else
                               {
                                    data=temp3;
                                    data[place2+1] = value;
                                    noOfItems++;
                                    firstCounter++;
                               }
                            }
                            else
                            {
                                data=temp3;
                                data[place1] = value;
                                noOfItems++;
                                firstCounter++;
                            }

                        }
                    }
                 }
             }

      }
      System.out.println("adding: "+value);
  }

  public void DeleteItem(int index)
  {
      if (index < noOfItems && index >= 0)
      {
          data[index] = null;
          if (data[index+1] != null)
          {
              int j = index;
              for(int i = (index+1); i<noOfItems; i++)
              {

                  data[j] = data[i];
                  j++;
              }
          }
          noOfItems--;
      }
      System.out.println("deleted: "+index);
  }


  public String toString()
  {
    return super.toString();
  }
}

非常感谢有关我如何做到这一点的任何提示。

亲切的问候，本。

Answer 1

实现加法 (binaryAdd) 与实现二分查找的方式几乎相同。代码将有 99% 的相似度。

假设您有以下数据:

+--------------------------+
|10|20|30|40|50|60|70|80|90|
+--------------------------+

您想向其中添加 35 并保持数据按升序排列。

中间值为 50，由于 35 < 50，我们感兴趣的是 10 到 50:

+--------------+
|10|20|30|40|50|
+--------------+

中间值是 30，因为 35 > 30，我们感兴趣的是 30 到 50:

+--------+
|30|40|50|
+--------+

中间值为 40，由于 35 < 40，我们感兴趣的是 30 到 40:

+-----+
|30|40|
+-----+

当你离开2个元素时，选择左边或右边进行比较:

if you choose left, 35 > 30, so 35 should be added after 30.
if you choose right, 35 < 40, so 35 should be before after 40.

这个过程类似于二分查找，但不是返回目标值的位置，而是返回插入值的位置。