增序数组插入元素 by JAVA

菜鸟上路之JAVA练手题30

/**
 * 题目：有一个已经排好序的数组。现输入一个数，要求按原来的规律将它插入数组中。
 * 分析： 1、首先判断此数是否大于最后一个数或者，然后再考虑插入中间的数的情况，插入后此元素之后的数，依次后移一个位置；
 * 		 2、大于最后一个数的情况比较简单，插入中间的情况采用了折半查找插入；
 * 		 3、之前考虑了输入小于第一个数的情况，后来发现多此一举。
 * 与折半查找不一样的地方是，本题中原序列已经是增序数列，只要考虑插入元素与序列中的元素关系即可
 * 总结：	1、数组大小不可以随意改变，开始天真的以为用一个append方法就能把新元素加入到数组中，这貌似是StringBuffer类的方法
 * 			2、开始想过先将输入元素加入到新数组中再直接使用折半插入排序，不过感觉好像与题意不符，因为先得出来的数列还是无序的
 */
import java.util.Scanner;

public class insertNum {
	
	public static void main(String[] args) {
		
		int x[] = {1, 2, 3, 4, 5, 7, 9, 21, 32};	//	定义一个增序数列
		int y[] = new int[x.length + 1];			//	定义一个空数组，长度比增序数组大一
		
		Scanner input = new Scanner(System.in);		//	输入一个整型
		System.out.print("请输入一个整数： ");
		int temp = input.nextInt();
		int low, high, mid;	
		
		if (temp >= x[x.length - 1]) {				//	输入整型大于最后一个数
			y[x.length] = temp;
			for (int i = 0; i < x.length; i++) {
				y[i] = x[i];
			}
			System.out.println("当输入大于或等于任意元素时的排序为： ");
			for (int a: y) {
				System.out.print(a + " ");
			}
			System.out.println();
//		} else if(temp <= x[0]) {					//	之前考虑了输入小于第一个数的情况，后来发现多此一举，整段垮掉	
//			y[0] = temp;
//			System.out.println("当输入小于或等于任意元素时的排序为： ");
//			for (int i = 0; i < x.length; i++) {
//				y[i + 1] = x[i];
//			}
//			for (int a: y) {
//				System.out.print(a + " ");
//			}
//			System.out.println();
		} else {
				low = 1; high = x.length - 2;				//折半查找范围
				while (low <= high) {						//查找条件，没有等号应该也可以，但是相关的数需要改动
					mid = (low + high)/2;
					if (x[mid] < temp) {					//查找右半子表
						low = mid + 1;
					}
					else {									//查找左半子表
						high = mid - 1;
					}
				}
				
				for (int j = high + 2; j < y.length; j++) {	//将x数组中比temp大的元素赋值给y数组
					y[j] = x[j - 1];
				} 
				for (int j = 0; j <= high; j++) {			//将将x数组中比temp小的元素赋值给y数组
					y[j] = x[j];
				}
				y[high + 1] = temp;							//将temp插入到相应位置
			}
			for (int a: y) {								//循环输出
				System.out.print(a + " ");
			}
	}
}