import java.util.Scanner;public class Main {static int flag = 0;static int[] print ;//數組一致性判斷public static boolean check(int[] a,int[] b) {for(int i=0;i<a.length;i++) {if(a[i] != b[i])return false;}return true;}//插入排序1 遞歸public static void insert(int[] a,int[] b,int start,int end,int length) {if(end < length) {//是否找完int index = end; //從后往前找int temp = 0;//查找最后一個元素應該插入到哪個位置，找到則退出循環for(int i=start;i<end;i++) {if (a[end] < a[i]) {index = i;temp = a[end];//找到位置后記住位置和需要挪動的數據break;}}//如果找到指定位置，則指定位置元素開始集體向后挪動一個單位，否則不變if(index != end) {for(int i = end-1;i>index-1;i--) {a[i+1] = a[i];}a[index] = temp;}end++;if(flag == 1) {System.out.println("Insertion Sort");for(int i=0;i<a.length;i++) {if(i<a.length-1)System.out.print(a[i] + " ");elseSystem.out.print(a[i]);}flag=0;return;}//與b串對比驗證if(check(a,b))flag = 1;insert(a,b,start, end, length);}}//插入排序2 非遞歸 從前往后//從第二個元素開始，每個元素只找他前面的，保證這個數一定比前面的大，public static void insertSort(int[] a){int i, j;int n = a.length;int target;//假定第一個元素被放到了正確的位置上//這樣，僅需遍歷1 - n-1for (i = 1; i < n; i++){j = i;target = a[i];while (j > 0 && target < a[j - 1]){//每比較一次就和前面的元素換一個位置a[j] = a[j - 1];j--;}a[j] = target;//與b串對比驗證for(int k=0;k<a.length;k++) {System.out.print(a[k] + " ");}System.out.println();} }//題意歸并排序//根據題意自制public static void mergeSort(int[][] a,int[] b) {int times = 0;//遞歸最大次數for(int i=1;i<a.length;i*=2)times++;//求次數int k = 0;//賦值次數//判斷迭代次數是否正確即是否為最后一次if(times>0) {for(int i=0,j=0;i<a.length;i+=2,j++) {//System.out.println("i="+i+" j="+j);if(i<a.length-1) {//判斷是否能夠兩個合成一個a[j] = mergeArray1(a[i], a[i+1]);}else {//不可以合成的話直接賦值a[j] = a[i];}//每次賦值完成都代表多添加一行k++;}int[][] temp= new int[k][];for(int i=0;i<temp.length;i++) {//添加完以后截斷源數組；改由新數組存儲temp[i] = a[i];}//輸出本次迭代完畢后的數列for(int i=0,p=0;i<temp.length;i++) {for(int j=0;j<temp[i].length;j++,p++) {print[p] = temp[i][j];} }if(flag == 1) {System.out.println("Merge Sort");for(int i=0;i<print.length;i++) {if(i<print.length-1)System.out.print(print[i] + " ");elseSystem.out.print(print[i]);}System.out.println();flag=0;return;}if(check(print,b))flag = 1;//迭代進行下次數列組合mergeSort(temp,b);}}//歸并排序任意長度的數組public static int[] mergeArray(int[] a,int[] b){//temp存放結果int[] temp = new int[a.length + b.length];//temp插入的次數int k=0;int k1 = 0;temp[0] = a[0];k++;for(int i=1;i<a.length;i++) {//放ak1 = k;for(int j = 0;j<temp.length;j++) {if(temp[j] > a[i]) {//后挪一位System.arraycopy(temp,j,temp,j+1,temp.length-j-1);temp[j] = a[i];k++;break;}}if(k1 == k) {temp[k] = a[i];k++;}}for(int i=0;i<b.length;i++) {//放bk1 = k;for(int j = 0;j<temp.length;j++) {if(temp[j] > b[i]) {//后挪一位System.arraycopy(temp,j,temp,j+1,temp.length-j-1);temp[j] = b[i];k++;break;}}if(k1 == k) {temp[k] = b[i];k++;}}return temp;}//歸并排序任意長度的兩個數組改進public static int[] mergeArray1(int[] a,int[] b){//temp存放結果int[] temp = new int[a.length + b.length];int i = 0; //a的索引int j = 0; //b的索引int k = 0; //temp的索引while(i<a.length && j<b.length) {if(a[i] <= b[j]) {temp[k] = a[i];i++;k++;}else {temp[k] = b[j];j++;k++;}}while(i<a.length) {temp[k] = a[i];k++;i++;}while(j<b.length) {temp[k] = b[j];k++;j++;}return temp;}//普通歸并排序,不符合題意public static void mergeSort(int[] array, int low, int high) {int mid = low+(high-low);if(high-low>1) mid = (int) (low + Math.sqrt(high - low)) ; // mid = (high + low)/2的另一種算法,避免溢出if(high-low ==1)mid = low;if(low < high) {mergeSort(array, low, mid); // 對array[low…mid]歸并排序 mergeSort(array, mid+1, high); // 對array[mid+1…high]歸并排序 mergeArray(array, low, mid, high);// 融合}return; }//普通歸并迭代方法，不符合題意public static void mergeArray(int[] array, int low, int mid, int high) {int[] temp = new int[mid-low+1]; //創建臨時數組,只需要創建前一半即可for(int i = 0, j = low; i < temp.length; i++, j++) {temp[i] = array[j]; //對臨時數組進行賦值}int i = 0, j = mid+1, m = low;while(i < temp.length && j <= high) { //將兩個有序數組歸并if(temp[i] <= array[j]) { //小于等于是為了維持穩定性array[m] = temp[i];i++; m++;continue;}else {array[m] = array[j];m++; j++;continue;}}while(i < temp.length) //最后將剩余的元素填充array[m++] = temp[i++];/*while(j <= high)array[m++] = array[j++];這一步其實可以不用做,因為此時array[j]==array[m]*/for(int r=low;r<=high;r++) {System.out.print(array[r]+" ");}System.out.println();}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int num = sc.nextInt();int[] a = new int[num];int[] b = new int[num];int[][] aa= new int[num][1];for(int i=0;i<num;i++) {a[i] = sc.nextInt();}for(int i=0;i<num;i++) {b[i] = sc.nextInt();}sc.close();for(int i =0;i<num;i++) {aa[i][0] = a[i];}print = new int[num];insert(a,b,0,1,num);mergeSort(aa,b);}}

總結

以上是生活随笔為你收集整理的PAT_B_1035_Java(25分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。