兩個有序數組合并為一個有序數組
突然想到了這個算法，記得以前看過，但是沒寫，怕自己會寫不出這個算法，于是就把它用JAVA寫出來，呵呵。
思想：先依次比較兩個數組，按照小的就傳入新的數組。當這次比較完之后可能有一個數組的長度很長，留下一些數組，然后在新數組的末尾插入即可。
代碼：
1 class ArraySort
2 {
3 //兩個有序數組的合并函數
4 public static int[] MergeList(int a[],int b[])
5 {
6 int result[];
7 if(checkSort(a) && checkSort(b)) //檢查傳入的數組是否是有序的
8 {
9 result = new int[a.length+b.length];
10
11 int i=0,j=0,k=0; //i:用于標示a數組 j：用來標示b數組 k：用來標示傳入的數組
12
13 while(i<a.length && j<b.length)
14 if(a[i] <= b[j]) {
15 result[k++] = a[i++];
16 }else{
17 result[k++] = b[j++];
18 }
19
20 /* 后面連個while循環是用來保證兩個數組比較完之后剩下的一個數組里的元素能順利傳入 */
21 while(i < a.length)
22 result[k++] = a[i++];
23 while(j < b.length)
24 result[k++] = b[j++];
25
26 return result;
27 }
28 else
29 {
30 System.out.print("非有序數組，不可排序！");
31 return null;
32 }
33 }
34
35 //檢查數組是否是順序存儲的
36 public static boolean checkSort(int a[])
37 {
38 boolean change = true; //這個標志位是一種優化程序的方法，可以看看我寫的冒泡排序優化就會明白了
39 for(int i=0; i<a.length-1 && change; i++)
40 {
41 for(int j=i+1; j<a.length; j++)
42 if(a[j-1] > a[j])
43 return false;
44 else change = false;
45 }
46 return true;
47 }
48
49 // 打印函數
50 public static void print(int b[])
51 {
52 for(int i=0; i<b.length ; i++)
53 {
54 System.out.print(b[i] + (i%10 ==9 ? "\n":"\t"));
55 }
56 }
57
58 public static void main(String args[])
59 {
60 int a[]={1,2,2,3,5,6,7,7};
61 int b[]={1,2,4,5,8,8,9,10,11,12,12,13,14};
62 int c[]= MergeList(a,b);
63 if(c!=null)
64 print(c);
65 else
66 System.out.println("");
67 }
68 }
2 {
3 //兩個有序數組的合并函數
4 public static int[] MergeList(int a[],int b[])
5 {
6 int result[];
7 if(checkSort(a) && checkSort(b)) //檢查傳入的數組是否是有序的
8 {
9 result = new int[a.length+b.length];
10
11 int i=0,j=0,k=0; //i:用于標示a數組 j：用來標示b數組 k：用來標示傳入的數組
12
13 while(i<a.length && j<b.length)
14 if(a[i] <= b[j]) {
15 result[k++] = a[i++];
16 }else{
17 result[k++] = b[j++];
18 }
19
20 /* 后面連個while循環是用來保證兩個數組比較完之后剩下的一個數組里的元素能順利傳入 */
21 while(i < a.length)
22 result[k++] = a[i++];
23 while(j < b.length)
24 result[k++] = b[j++];
25
26 return result;
27 }
28 else
29 {
30 System.out.print("非有序數組，不可排序！");
31 return null;
32 }
33 }
34
35 //檢查數組是否是順序存儲的
36 public static boolean checkSort(int a[])
37 {
38 boolean change = true; //這個標志位是一種優化程序的方法，可以看看我寫的冒泡排序優化就會明白了
39 for(int i=0; i<a.length-1 && change; i++)
40 {
41 for(int j=i+1; j<a.length; j++)
42 if(a[j-1] > a[j])
43 return false;
44 else change = false;
45 }
46 return true;
47 }
48
49 // 打印函數
50 public static void print(int b[])
51 {
52 for(int i=0; i<b.length ; i++)
53 {
54 System.out.print(b[i] + (i%10 ==9 ? "\n":"\t"));
55 }
56 }
57
58 public static void main(String args[])
59 {
60 int a[]={1,2,2,3,5,6,7,7};
61 int b[]={1,2,4,5,8,8,9,10,11,12,12,13,14};
62 int c[]= MergeList(a,b);
63 if(c!=null)
64 print(c);
65 else
66 System.out.println("");
67 }
68 }
總結：這個算法應該算是經典的了，一定要記住，這一部分應該是數據結構中的鏈表中的內容。
浙公網安備 33010602011771號