利用二分法插入一个数据,数据总是无法达到有序的效果

主要问题出现在insertElement()方法,其中记录插入数据的midPos始终有问题。始终是会移动有问题。请帮忙看一下。

 /**
 * Description:
 * <br>本程序主要实现一个包含有序数组类。
 * <br>主要目的:将数组封装起来,然后,外界只能利用提供出去的接口方法,访问数组。
 * <br>Program Name:OrderArray
 * <br>Date:2015-09-20
 * @author WayneZhao
 * @version 1.0
*/
import java.util.Scanner;

class OrderArray
{
    private int[] array;
    private int nIndex;//数组元素的下标

    /**
    * 无参数构造器
    */
    public OrderArray()
    {
        System.out.println("数组必须要有长度!");
    }

    /**
    * 带一个int类型参数的构造器
    * <br>用于告诉类,数组有多长
    * @param maxSize 该参数用于指定数组的长度
    */
    public OrderArray(int maxSize)
    {
        this.array = new int[maxSize];
        this.nIndex = 0;
    }

    /**
    * 展示数组中的每一个元素
    */
    public void display()
    {
        for(int i = 0; i < nIndex;i++)
        {
            System.out.print("" + array[i] + '\t');
        }
        System.out.println("");
    }

    /**
    * 在数组中寻找一个元素
    * <br>此为二分法寻找数组中的元素
    * @param value 该参数用于表示需要找寻值
    * @return 返回数组的索引值
    */
    public int findElementBinary(int value)
    {
        int headerPos = 0;
        int railPos = nIndex-1;

        while(headerPos < railPos)
        {
            int midPos = (headerPos + railPos)/2;

            if(value == array[midPos])
                return midPos;
            else if(value < array[midPos])
                railPos = midPos-1;
            else
                headerPos = midPos+1;
        }

        return -1;
    }

    /**
    * 向数组中插入一个元素
    * @param value 该参数用于向数组中插入一个元素
    */
    public void insertElement(int value)
    {
        /*
        int pos;//设置一个变量,记录插入的位置
        //1st,遍历里数组,确定元素所需要插入的位置
        for(pos = 0;pos<nIndex;pos++)
            if(value<array[pos])
                break;
        */

        if(nIndex == 0)
        {
            System.out.println("[fillData]nIndex="+nIndex);
            array[0] = value;
        }
        else if(nIndex == 1)
        {
            System.out.println("[fillData]nIndex="+nIndex);
            if(value < array[0])
            {
                array[1]=array[0];
                array[0]=value;
            }
            else
            {
                array[1]=value;
            }
        }
        else
        {
            System.out.println("[fillData]nIndex="+nIndex);
            if(value < array[0])
            {
                System.out.println("[fillData]"+value+"比"+array[0]+"小");
                for(int j = nIndex;j>0;j--)
                    array[j] = array[j-1];
                array[0] = value;
            }
            else if(value > array[nIndex-1])
            {
                System.out.println("[fillData]"+value+"比"+array[nIndex-1]+"大");
                array[nIndex]=value;
            }
            else
            {
                int midPos = 0;//定义中间位置
                int headPos = 0,tailPos = nIndex-1;//定义起始位置

                System.out.println("[fillData]插入的元素为"+value);
                System.out.println("[fillData]headPos初始"+headPos);
                System.out.println("[fillData]tailPos初始"+tailPos);
                System.out.println("[fillData]midPos初始"+midPos);

                while(headPos<tailPos)
                {
                    System.out.println("[fillData]现在开始进行二分法");
                    midPos = (headPos+tailPos)/2;

                    System.out.println("[fillData]结果如下:");
                    System.out.println("[fillData]二分中headPos="+headPos);
                    System.out.println("[fillData]二分中tailPos="+tailPos);
                    System.out.println("[fillData]二分中midPos="+midPos);
                    System.out.println("------------------------------");

                    if(value<array[midPos])
                    {
                        System.out.println("[fillData]二分中");
                        System.out.println("[fillData]"+value+"比"+array[midPos]+"小");
                        System.out.println("[fillData]移动tailPos");
                        System.out.println("[fillData]tailPos=midPos-1");
                        tailPos=midPos-1;
                    }
                    else
                    {
                        System.out.println("[fillData]二分中");
                        System.out.println("[fillData]"+value+"比"+array[midPos]+"大");
                        System.out.println("[fillData]移动headPos");
                        System.out.println("[fillData]headPos=midPos+1");
                        headPos=midPos+1;
                    }

                    System.out.println("[fillData]移动之后的结果:");
                    System.out.println("[fillData]二分中headPos="+headPos);
                    System.out.println("[fillData]二分中tailPos="+tailPos);
                    System.out.println("[fillData]二分中midPos="+midPos);
                    System.out.println("------------------------------");
                }

                //进行插入动作
                for(int j = nIndex;j>midPos;j--)
                    array[j] = array[j-1]; 

                array[midPos] = value;
            }
        }

        nIndex++;
    }

    /**
    * 在数组中删除一个元素
    * @param value 该参数用于表示需要删除的元素
    * @return 返回是否删除成功
    */
    public boolean deleteElement(int value)
    {
        int indexTemp = findElementBinary(value);
        if(indexTemp == -1)
            return false;
        else
        {
            for(int j = indexTemp;j<nIndex-1;j++)
            {
                array[j] = array[j+1];
            }
            nIndex--;
            return true;
        }
    }
}

public class OrderArrayAdvance
{
    public static void main(String[] args)
    {
        Scanner sc_maxSize = new Scanner(System.in);
        System.out.println("你希望数组的长度有多长?");
        int maxSize = sc_maxSize.nextInt();
        OrderArray oaOne = new OrderArray(maxSize);
        System.out.println("我们已经得到一个长度为"+maxSize+"的数组");


        System.out.println("现在我们需要填充它。");
        System.out.println("这里使用1到100的随机数来填充它");


        for(int i = 0;i<maxSize;i++)
        {
            int tempInt = (int)(Math.random()*100+1);
            oaOne.insertElement(tempInt);

            System.out.println("[fillData]填充好的数组如下");
            oaOne.display();
        }


        /* 
        oaOne.insertElement(1);
        System.out.println("[fillData]填充好的数组如下");
        oaOne.display();        
        oaOne.insertElement(3);
        System.out.println("[fillData]填充好的数组如下");
        oaOne.display();        
        oaOne.insertElement(7);
        System.out.println("[fillData]填充好的数组如下");
        oaOne.display();
        oaOne.insertElement(9);
        System.out.println("[fillData]填充好的数组如下");
        oaOne.display();
        oaOne.insertElement(5);
        System.out.println("[fillData]填充好的数组如下");
        oaOne.display();
         */

        System.out.println("填充好的数组如下");
        oaOne.display();
    }
}
查看全部
a80C51
BatmanWayne
2015/09/19 17:23
  • java
  • 二分法
  • 插入数据
  • 插入位置
  • 点赞
  • 收藏
  • 回答
    私信

2个回复