Java数据结构与算法之有序数组的插入和合并

我不是女神ヾ 2022-08-08 19:58 91阅读 0赞

package com.wayne.example.OrderArray;
    
    public class OrderArray { 
    
        private int[] orderArray;
        private int elementPos;
    
        /** * 数组初始化，初始化数组的长度 * @param maxSize 数组的长度 */
        public OrderArray(int maxSize) {
            orderArray = new int[maxSize];
            elementPos = 0;
        }
    
        /** * 获取数组长度，用于获取数组的长度 * @return 返回数组的长度 */
        public int size(){
            return elementPos;
        }
    
        /** * 插入元素，用于向数组中插入元素 <br> * 利用二分法插入元素 * @param value 待插入的元素值 */
    
        /* * 主要思想是 * 1，数组怎么从一个数变成两个数 * 2，本身数组有序的话，为了节省时间，我们可以先判断下与他相邻的那个值是否满足条件。 * 换言之，如果插入的元素比中间值大，但又比中间值的下一个元素小，则插入的位置就是中间值的下一个值。 * 3，二分法结束的最基本条件是头索引值大于尾索引值。 */
        public void insertElementsBin(int value) {
    
            if(elementPos == 0)//如果是第一次插入，此时数组的元素都是空的。可以直接插入
            {
                orderArray[elementPos] = value;
            }
            else
            {
                int headPos = 0,tailPos = elementPos - 1;
                int midPos = 0;
    
                while(headPos <= tailPos)
                {
                    midPos = (headPos+tailPos)/2;
    
                    if(value == orderArray[midPos])
                        break;
                    else if(value > orderArray[midPos])
                    {
                        if(midPos == elementPos-1)
                        //如果基础数组只有一个元素时，则直接插入对应的位置
                        {
                            midPos+=1;
                            break;
                        }
                        else if(orderArray[midPos+1] >= value)
                        //因为它是一个线性数组，故如果与其相邻的值已经比目标值大了，则此时插入的数据的位置也就找到了
                        //也就是midPos+1的位置
                        {
                            midPos+=1;
                            break;
                        }
                        else
                        //如果上述条件不满足，则移动脚标
                        {
                            headPos = midPos+1;
                        }
                    }
                    else
                    {
                        if(midPos == 0)
                            //如果基础数组只有一个元素时，则直接插入对应的位置
                            break;
                        else if(orderArray[midPos-1]<=value)
                            //因为它是一个线性数组，故如果与其相邻的值已经比目标值小了，则此时插入的数据的位置也就找到了
                            //也就是midPos的位置
                            break;
                        else
                            tailPos = midPos-1;
                    }
                }
    
                //执行插入的动作。。。 
                for(int i = elementPos;i>midPos;i--)
                    orderArray[i] = orderArray[i-1];
    
                orderArray[midPos] = value;
            }
    
            elementPos++; // increment size 
    
        }
    
        /** * 显示数组，用于显示数组中的元素 */
        public void displayElements() {
            System.out.print("[");
    
            for(int i = 0;i<elementPos-1;i++)
                System.out.print(orderArray[i]+", ");
    
            System.out.println(orderArray[elementPos-1]+"]");
        }
    
        /** * 查找元素，用于查找数组中指定的元素 <br> * 利用二分法进行查找 * @param value 需要查找的数值 * @return 返回数据在数组中的索引值。如果没有找到，则返回 -1. */
        public int findElements(int value) {
            int headPos = 0;
            int tailPos = elementPos - 1;
    
            while(headPos <= tailPos)
            {
                int midPos = (headPos + tailPos)/2;
    
                if(value == orderArray[midPos])
                    return midPos;
                else if( value < orderArray[midPos])
                    tailPos = midPos - 1;
                else
                {
                    headPos = midPos + 1;
                }
            }
    
            return -1;
        }
    
        /** * 获取元素，用于获取该索引值对应的数组的元素 * @param index 数组索引值 * @return 如果索引值符合条件，则返回该索引值对应的数据；如果不符合条件，则返回-1 */
        public int getPosElements(int index)
        {
            if(index > elementPos)
            {
                System.out.println("你输入的索引值太大，悲了个具！");
                return -1;
            }
            return orderArray[index];
        }
    
        /** * 删除数据，用于删除数组中指定的元素<br> * @param value 需要删除的元素 * @return 返回是否删除成功。如果删除成功，则返回true;如果删除不成功，就返回false */
        public boolean deleteElements(int value){
    
            int posTemp = findElements(value);
    
            if(posTemp == -1)
                return false;
            else
            {
                for(int i = posTemp;i<elementPos-1;i++)
                    orderArray[i] = orderArray[i+1];
                elementPos--;
    
                return true;
    
            }
        }
    
        /** * 合并数组，用于将一个数组插入到另外一个数组中 * @param srcOneOrderArray 源数组一 * @param srcTwoOrderArray 源数组二 * @return 返回插入完成之后的数组 */
        /* * 思路: * 将数组一中的元素按顺序抽取出来， * 每抽取一次，则和数组二中的第一个元素进行比较， * 将较小的那个元素放到最终数组中。 * 被抽取元素的数组，要进行裁剪，保证该数组中的第一元素始终是该数组中最小的那个。 * 如此循环，直至其中任意一个数组的长度为零结束。 * 若一个数组长度为零，而另外一个数组还有元素时， * 直接将多的元素依次插入到最终数组中。 * 如此，即可完成该数组合并的功能。 */
        public static OrderArray merge( OrderArray srcOneOrderArray,OrderArray srcTwoOrderArray)
        {
            OrderArray resultOrderArray = 
                    new OrderArray(srcOneOrderArray.size()+srcTwoOrderArray.size());
    
            while((srcOneOrderArray.size() != 0)&&(srcTwoOrderArray.size() != 0))
            {
                int tempInt = 0;
    
                if(srcOneOrderArray.getPosElements(0)<=srcTwoOrderArray.getPosElements(0))
                {
                    tempInt = srcOneOrderArray.getPosElements(0);
                    srcOneOrderArray.deleteElements(tempInt);
                }
                else
                {
                    tempInt = srcTwoOrderArray.getPosElements(0);
                    srcTwoOrderArray.deleteElements(tempInt);
                }
    
                resultOrderArray.insertElementsBin(tempInt);
            }
    
            if(srcOneOrderArray.size() != 0)
                for(int i = 0;i<srcOneOrderArray.size();i++)
                    resultOrderArray.insertElementsBin(srcOneOrderArray.getPosElements(i));
    
            if(srcTwoOrderArray.size() != 0)
                for(int i = 0;i<srcTwoOrderArray.size();i++)
                    resultOrderArray.insertElementsBin(srcTwoOrderArray.getPosElements(i));
    
            return resultOrderArray;
        }
    }