冒泡排序
冒泡排序（Bubble Sort），看到這種算法，我就想起一句話“小數上浮，大數下沉”，通過層層的比較使小數浮出水面，而使大數“石沉水底”。從而達到排序的效果。冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
冒泡排序算法的運作如下:
1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
3. 針對所有的元素重復以上的步驟，除了最后一個。
4. 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
冒泡排序的過程圖：
實例代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public class BubbleSort{ public static int[] bubbleSort(int[] array){ for(int i = 0;i < array.length;i++){ for(int j = 0; j < array.length-i-1;j++){ if(array[j] > array[j+1]){ int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } System.out.println("第"+(i+1)+"趟排序"); for(int k = 0;k < array.length;k++){ System.out.print(array[k]+" "); } System.out.println(); } return array; } /** * @param args */ public static void main(String[] args){ int[] array = {7,3,9,5,6,8,1}; bubbleSort(array); }} |
打印結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
第1趟排序3 7 5 6 8 1 9第2趟排序3 5 6 7 1 8 9第3趟排序3 5 6 1 7 8 9第4趟排序3 5 1 6 7 8 9第5趟排序3 1 5 6 7 8 9第6趟排序1 3 5 6 7 8 9第7趟排序1 3 5 6 7 8 9 |
二分查找
排好順序了，也需要我們查找我們想要的數據了，而二分法查找就是其中常用的，節時的，基礎的一種算法。二分查找就是從排序好數據的中間位置進行查找比較，類似于木棒的中間對砍，所以又叫折半查找，它是一種效率較高的查找方法。
【二分查找要求】：1.必須采用順序存儲結構 2.必須按關鍵字大小有序排列。
【優缺點】折半查找法的優點是比較次數少，查找速度快，平均性能好;其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。
【算法思想】首先，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。
重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
【算法復雜度】假設其數組長度為n，其算法復雜度為o（log（n）），最壞情況下的時間復雜度是O(n)。
實例代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
package com.somnus.array;/** * 二分查找法 * @author Compaq * */public class BinarySearch{ public static int binarySearch(int[] array, int value){ int low = 0; int high = array.length-1; int middle = 0; while(low <= high){ middle = (low+high)/2;//0 6 4 6 6 6 for(int i = 0;i < array.length;i++){ System.out.print(array[i]+" "); if(i == middle)//3 5 6 緊隨最中間的指向 后面 打印分隔符 { System.out.print("## "); } } System.out.println(); if(array[middle] == value){ return middle; } if(value < array[middle]){ high = middle - 1; } if(value > array[middle]){ low = middle + 1; } } return -1; } /** * @param args */ public static void main(String[] args){ int[] array = {7,3,9,5,6,8,1}; int[] array1 = BubbleSort.bubbleSort(array); int index = binarySearch(array1,1); System.out.println("所在的位置:"+index); }} |
打印結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
第1趟排序3 7 5 6 8 1 9第2趟排序3 5 6 7 1 8 9第3趟排序3 5 6 1 7 8 9第4趟排序3 5 1 6 7 8 9第5趟排序3 1 5 6 7 8 9第6趟排序1 3 5 6 7 8 9第7趟排序1 3 5 6 7 8 91 3 5 6 ## 7 8 91 3 ## 5 6 7 8 91 ## 3 5 6 7 8 9所在的位置:0 |
分析總結
查找算法中，二分法是速度最快的，但是必須是有序的序列。這些都是算法的基礎中的基礎，還需要我們下大功夫來試驗，來總結，來吸收，堅持算法學習中.
