選擇排序
選擇排序是從數(shù)組下標(biāo)0（下標(biāo)為0的元素）開始依次固定與之后的所有元素進(jìn)行比較，比被固定的元素小則與之交換欧漱，否則不交換，一輪下來可以確定出被固定下標(biāo)的元素是排在第一位的元素即最小的元素
冒泡排序
比較相鄰的元素葬燎。如果第一個(gè)比第二個(gè)大误甚，就交換他們兩個(gè)。
對每一對相鄰元素作同樣的工作谱净，從開始第一對到結(jié)尾的最后一對靶草。在這一點(diǎn)，最后的元素應(yīng)該會是最大的數(shù)岳遥。
針對所有的元素重復(fù)以上的步驟奕翔，除了最后一個(gè)。
持續(xù)每次對越來越少的元素重復(fù)上面的步驟浩蓉，直到?jīng)]有任何一對數(shù)字需要比較派继。
二分法查找
二分法查找是建立在已經(jīng)排好序的前提下，確定該區(qū)間的中間位置K（2）將查找的值T與array[k]比較捻艳。若相等驾窟，查找成功返回此位置；否則確定新的查找區(qū)域认轨，繼續(xù)二分查找绅络。區(qū)域確定如下：a.array[k]>T 由數(shù)組的有序性可知array[k,k+1,……,high]>T;故新的區(qū)間為array[low,……，K-1]b.array[k]<T 類似上面查找區(qū)間為array[k+1,……嘁字，high]恩急。每一次查找與中間值比較，可以確定是否查找成功纪蜒，不成功當(dāng)前查找區(qū)間縮小一半衷恭，遞歸找，即可纯续。時(shí)間復(fù)雜度:O(log2n)
public class Sort {
public static void main(String args[]) {
int[] arr = { 4, 56, 23, 166, 2 };
// selectSort(arr); //選擇排序
// bubbly(arr); //冒泡排序
Arrays.sort(arr); // JDK自身的排序
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
// 二分法查找
int key = 56;
int index = halfSearch(arr, key);
System.out.println(index);
}
// 選擇排序
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
exchange(arr, i, j);
}
}
}
}
// 冒泡排序
public static void bubbly(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
exchange(arr, j, j + 1);
}
}
}
}
// 交換
public static void exchange(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 二分法查找（數(shù)組必須是已經(jīng)排好序的）
public static int halfSearch(int[] arr, int key) {
int min = 0, max = arr.length - 1, mid;
while (min <= max) {
mid = (min + max) / 2;
if (key > arr[mid])
min = mid + 1;
else if (key < arr[mid])
max = mid - 1;
else
return mid;
}
return -1;
}
}
