常用算法
1.冒泡排序:
原理：比較兩個相鄰的元素，將值大的元素交換至右端
示例:
public static void bubbleSort(int[] a) {int n = a.length;//總共進行n-1輪的比較for (int i = 1; i < n; i++) {for (int j = 0; j < n - i; j++) {if (a[j] > a[j + 1]) {//交換int temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}} }
2.選擇排序：
原理：每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列最后，直到全部記錄排序完畢。
示例:
public static void selectionSort(int[] a) { for(int i = 0; i < a.length - 1; i++) {// 做第i趟排序int m = i;for(int j = i + 1; j < a.length; j++){// 選最小的記錄if(a[j] < a[m]){m = j; //記下目前找到的最小值所在的位置 }}if(i != m){ //交換a[i]和a[m]int temp = a[i];a[i] = a[m];a[m] = temp;}} }
3.插入排序:
原理：從數組的第一個元素a[0]開始，將其后一個元素a[1]插入到a[0]的前面或者后面，接著繼續這一過程。每次都是將a[i]插入到已經排序好的a[0]~a[i-1]中合適的位置
示例:
public static void insertSort(int[] a) {for (int i = 1; i < a.length; i++) {for (int j = i; j > 0; j--) {if (a[j] < a[j - 1]) {int temp = a[j];a[j] = a[j - 1];a[j - 1] = temp;} else {break;}}} }
4.快速排序:
- 快速排序是對冒泡排序的一種改進
- 思想：在數組中找出適當的軸心，然后將數組一分為二，分別對左邊與右邊數組進行排序
二分查找
- 前提條件： 已排序的數組中查找
- 二分查找的基本思想是:
–?首先確定該查找區間的中間點位置：?int mid = (low+upper) / 2;
–?然后將待查找的值與中間點位置的值比較：
-
- 若相等，則查找成功并返回此位置。
- 若中間點位置值大于待查值，則新的查找區間是中間點位置的左邊區域。
- 若中間點位置值小于待查值，則新的查找區間是中間點位置的右邊區域。下一次查找是針對新的查找區間進行的。
示例:
public static int binarySearch(int[] a, int num) {int low = 0; // 起點int upper = a.length - 1; // 終點while (low <= upper) {int mid = (low + upper) / 2; // 中間點if (a[mid] < num) { // 中間點的值小于要查找的值low = mid + 1; // 更改查找的起點為中間點位置后一位} else if (a[mid] > num) { // 中間點的值大于要查找的值upper = mid - 1; // 更改查找的終點為中間點位置前一位} else { // 中間點的值等于要查找的值return mid; // 返回該位置 }}return -1; }
數組幫助類Arrays
- java.util.Arrays 數組操作工具
public static void sort(int[] a); //經過調優的快速排序法 public static int binarySearch(int[] a, int key); //使用二分搜索法
二維數組
- Java并沒有真正的多維數組，二維數組可以看成以數組為元素的數組。如：
int [][] a = { {1}, {4,5,6}, {7,8}}; ?
