怎样在有序的数组中插入一个元素呢？并打印出来~~

1.     static int[] insertArray(int a[], int key)
   
2.     {
   
3.        int i,j;
   
4.        int b[];
   
5.        i=a.length-1;
   
6.        b=new int[a.length+1];//申请一个更大的空间
   
7.       
   
8.        Arrays.sort(a);//使用java.util.Arrays.sort 方法对一个数组进行排序
   
9.       
   
10.       //找到插入位置i
    
11.        while(i>=0 && key<a[i])
    
12.            i--;
    
13.        if(i<0)
    
14.        {
    
15.            b[0]=key;
    
16.            for(j=1;j<=a.length;j++)
    
17.               b[j]=a[j-1];     //i<0说明key比a[]中所有值都小，所以插在数组最前面
    
18.        }
    
19.        else
    
20.        {
    
21.        for(j=0;j<=i;j++)
    
22.        {
    
23.            b[j]=a[j];    //a[0....i] copy 到b[0....i]
    
24.        }
    
25.        b[i+1]=key;
    
26.        for(j=i+2;j<=a.length;j++)
    
27.            b[j]=a[j-1];
    
28.        }
    
29.        return b;
    
30.             
    
31.     }

复制代码

陈冲 发表于 2012-7-8 13:56

是不是相当于在折半查找法下进行插入操作呢~~

龚建锋 发表于 2012-7-8 14:09
是不是相当于在折半查找法下进行插入操作呢~~

呵呵 你说的很对，因为利用折半查找的前提条件就是数组为有序的，而所谓有序数组中插入元素，目前为止可以说等价于折半查找法下进行插入操作~~~！

import java.util.*;
public class Text {
       
        public static void main(String[] args) {
       
        int[]num={1,3,4,6,7};
        int s=2;
        //将数组num和整数s传给Info作为参数并调用该方法
        Info(num,s);
        }
               
        //定义一个有数组num1（即插入整数前的数组），有整数（该整数是要插入数组的数字）的参数的方法
        public static void Info(int[]num1,int a){
                //定义一个新数组，该数组比原数组的长度大1（因为插入的整数需要占用一个位置）
                int[]num2=new int[num1.length+1];
                //运用for循环将num1数组中的值赋给新数组num2；
                for(int i=0;i<num1.length;i++){
                        num2[i]=num1[i];
                }
                //将插入的整数a放在新数组num2的最后一个位置
                num2[num2.length-1]=a;//此时num2的数据是无序的
                Arrays.sort(num2);//根据java的特有方法Arrays.sort()对num2的数据进行排序
               
                //for循环输出排序后数组num2的值
                for(int i=0;i<num2.length;i++){
                        System.out.println(num2[i]);
                }
        }
}

import java.util.*;
public class Text {

public static void main(String[] args) {

int[]num={1,3,4,6,7};
int s=2;
//将数组num和整数s传给Info作为参数并调用该方法
Info(num,s);
}


  /*
定义一个有数组num1（即插入整数前的数组），有整数（该整数是要插入数组的数字）的参数的方法
*/
public static void Info(int[]num1,int a){

          int[]num2=new int[num1.length+1]; //定义一个新数组，该数组比原数组的长度大1（因为插入的整数需要占用一个位置）

           //运用for循环将num1数组中的值赋给新数组num2；
          for(int i=0;i<num1.length;i++){
                num2=num1;
           }
           //将插入的整数a放在新数组num2的最后一个位置
            num2[num2.length-1]=a;//此时num2的数据是无序的
            Arrays.sort(num2);//根据java的特有方法Arrays.sort()对num2的数据进行排序
  
            //for循环输出排序后数组num2的值
            for(int i=0;i<num2.length;i++){
                  System.out.println(num2);
            }
       }
}

怎样在有序的数组中插入一个元素呢？并打印出来~~
====================
其实这个问题毕老师视频里有讲解，只是没有实现插入的操作，因为数组插入操作不如链表效率高。
就这个问题而言，既然是有序数组（即使无序，用Array.sort();也能轻易实现）。那只要3步操作。
1.求出要插入的数据在新数组中的位置。即折半查找也好，依次比较也好。
2.将插入数据之后的原数组中的元素依次后移一格存入新数组。即脚标依次+1即可。
3.将排列好的新的元素顺序依次插入新数组。插入元素之前的元素脚标不变。
具体代码不难实现，希望楼主自己动手解决问题，加深印象。
就像毕老师所说，有些问题先想清楚具体步骤，再思考如何用代码实现，会比较简单。
希望帮到你了~~

想法一：
1，建立一个比已知数组多一个元素的数组
2，将key插入到新数组的最后
3，对新数组排序Arrays.sort(b)
4，输出
import java.util.*;
class demo
{
        public static void main(String[] args)
        {
        int [] arr={2,3,5,6,7,9};
        int key=4;
        insarr(arr,key);
        }

public static void insarr(int[] arr,int key)
{
        int [] b=new int[arr.length+1];//定义比arr多一个数的数组
        b[arr.length]=key;//将key存到b数组的最后一位
        for (int x=0; x<=arr.length-1;x++)//将arr拷贝到b数组中
        {
                b[x]=arr[x];
        }

        Arrays.sort(b);//对b排序
        for (int x=0; x<=b.length-1;x++)//打印b数组
        {
                System.out.print(b[x]);
        }
        return;
}
}
想法二：
1，建立一个比给定数组多一个元素的数组，（给定为a，新的为b）
2，遍力a数组的每个元素，与key相比，写入b数组
     这里只有三种情况：
     a数组元素小于key，b数组［a数组脚标］值=a数组元素脚标值，
     a数组元素等于key，b数组［a数组脚标］值=key，b数组［a数组脚标+1］=a数组元素脚标值
     a数组元素大于key，b数组［a数组脚标+1］=a数组元素，
3，输出b数组
如有错，请指出{:soso_e113:}

想法二有点问题，a数组中没有的。需要加个已经存入的标志。水平有限...