Java學習 （七）、數組，查找算法，二分查找法，冒泡排序，選擇排序，插入排序，java冒泡
一、常用數組查找算法
工作原理：它又稱為順序查找，在一列給定的值中進行搜索，從一端的開始逐一檢查每個元素，知道找到所需元素的過程。
例1：查找指定的數在數組中出現的位置，找到返回下標，找不到返回-1
![]()
1 import java.util.Scanner;
2 public class LinearSearch{
3 public static void main(String []argas)
4 {
5 int [] array={10,100,90,65,80,92};
6 System.out.println("請輸入要獲取的數");
7 Scanner input=new Scanner(System.in);
8 int number=input.nextInt();
9 int index=-1;//找到數組中所在數的下標，找不到等於-1
10 for(int i=0;i<array.length;i++)
11 {
12 if(array[i]==number)
13 {
14 index=i+1;
15 break;
16 }
17 }
18 if(index!=-1)
19 {
20 System.out.println("找到該數字，在數組中的第"+index+"位置");
21 }
22 else
23 {
24 System.out.println("要查找的數字不存在");
25 }
26 }
27 }
View Code
例2：求數組中的最大值，最小值
![]()
1 public class LinearSearch{
2 public static void main(String []argas)
3 {
4 int [] array={10,100,90,65,80,92};
5 //求數組中的最大值，最小值
6 int max=array[0];//最大值
7 int min=array[0];//最小值
8 for(int i=1;i<array.length;i++)
9 {
10 if(max<array[i])
11 {
12 max=array[i];
13 }
14 if(min>array[i])
15 {
16 min=array[i];
17 }
18 }
19 System.out.println("該數組的最大值為"+max+",最小值為"+min);
20 }
21 }
View Code
二、二分查找法
工作原理：它又稱為折半查找法，將數組中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將數組分成前、後兩個子數組，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子數組，否則進一步查找後一子數組。重復以上過程，直到找到或找不到為止。
注：針對有序數組
![]()
1 import java.util.Scanner;
2 public class LinearSearch{
3 public static void main(String []argas)
4 {
5 int[] array2={1,2,3,4,5,10,15,18,19,22};
6 System.out.println("請輸入要獲取的數");
7 Scanner input=new Scanner(System.in);
8 int number=input.nextInt();
9 int index=-1;//找到數組中所在數的下標，找不到等於-1
10 int start=0;//起始下標
11 int end=array2.length-1;//終止下標
12 int middle;
13 while(start<=end)
14 {
15 //找到中間下標所對應的元素值
16 middle=(start+end)/2;
17 int number2=array2[middle];
18 //假如要查找的那個數大於中間比較的那個數
19 //去掉左邊的數
20 if(number>number2)
21 {
22 start=middle+1;
23 }
24 //保留左邊的數，去掉右邊的數
25 else if(number<number2)
26 {
27 end=middle-1;
28 }
29 else
30 {
31 index=middle+1;
32 break;
33 }
34 }
35 if(index!=-1)
36 {
37 System.out.println("找到該數字，在數組中的第"+index+"位置");
38 }
39 else
40 {
41 System.out.println("要查找的數字不存在");
42 }
43
44 }
45 }
View Code
三、冒泡排序法
工作原理：比較相鄰的元素，如果第一個比第二個大，就交換它們兩個。對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。最後的元素應該會是最大的數。針對除了最後一個元素以外所有的元素重復以上的步驟。直到沒有任何一對數字需要比較。
![]()
1 public class BubbleSort{
2 public static void main(String []argas)
3 {
4 int[] array={80,53,12,90,35,22,65,45,82,33};
5 //N個數比較的輪數為N-1次
6 for(int i=0;i<array.length-1;i++)
7 {
8 //每一輪比較的次數為N-1-i次
9 for(int j=0;j<array.length-i-1;j++)
10 {
11 //比較相鄰的2個數，小靠前
12 if(array[j]>array[j+1])
13 {
14 //兩個數做交換，通過設置臨時變量
15 int temp=array[j];
16 array[j]=array[j+1];
17 array[j+1]=temp;
18 }
19 }
20 }
21 //把排好序的數組輸出
22 for(int i=0;i<array.length;i++)
23 {
24 System.out.print(array[i]+",");
25 }
26 }
27 }
View Code
四、選擇排序法
工作原理：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然後，再從剩余未排序元素中繼續尋找最小元素，然後放到排序序列末尾。以此類推，直到所有元素均排序完畢。
![]()
1 public class SelectSort{
2 public static void main(String []argas)
3 {
4 int[] array={80,53,12,90,35,22,65,45,82,33};
5 int min=0;//保存最小元素值的下標
6 //N個數比較的輪數為N-1次
7 for(int i=0;i<array.length-1;i++)
8 {
9 min=i;
10 //查找最小數在數組中的下標
11 for(int j=i+1;j<array.length;j++)
12 {
13 if(array[min]>array[j])
14 {
15 min=j;//保存最小數的下標
16 }
17 }
18 //如果第i個數位置不在i上，則進行交換
19 if(i!=min)
20 {
21 int temp=array[i];
22 array[i]=array[min];
23 array[min]=temp;
24 }
25 }
26
27 for(int i=0;i<array.length;i++)
28 {
29 System.out.print(array[i]+",");
30 }
31 }
32 }
View Code
五、插入排序法
工作原理：它是通過構建有序序列，對於為排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。
![]()
1 public class InsertSort{
2 public static void main(String []argas)
3 {
4 int[] array={80,53,12,90,35,22,65,45,82,33};
5 for(int i=1;i<array.length;i++)
6 {
7 int temp=array[i];
8 //把下標保存起來
9 int j=i;
10 while(j>0&&temp<array[j-1])
11 {
12 //上面的數覆蓋其下面的數
13 array[j]=array[j-1];
14 j--;
15 }
16 array[j]=temp;//插入數據
17 }
18
19 for(int i=0;i<array.length;i++)
20 {
21 System.out.print(array[i]+",");
22 }
23 }
24 }
View Code
