二分查找
又叫折半查找浇冰，要求待查找的序列有序。每次取中間位置的值與待查關(guān)鍵字比較洋魂，如果中間位置的值比待查關(guān)鍵字大槐秧，則在前半部分循環(huán)這個查找的過程，如果中間位置的值比待查關(guān)鍵字小忧设，則在后半部分循環(huán)這個查找的過程刁标。直到查找到了為止，否則序列中沒有待查的關(guān)鍵字
public static int biSearch(int[] array, int a) {
????int lo =0;
? ? int hi = array.length -1;
? ? int mid;
? ? while (lo <= hi) {
mid = (lo + hi) /2;//中間位置
? ? ? ? if (array[mid] == a) {
return mid;
? ? ? ? }else if (array[mid] < a) {//向右查找
? ? ? ? ? ? lo = mid +1;
? ? ? ? }else {//向左查找
? ? ? ? ? ? hi = mid -1;
? ? ? ? }
}
return -1;
}
冒泡排序算法
（1）比較前后相鄰的二個數(shù)據(jù)址晕，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)膀懈，就將這二個數(shù)據(jù)交換。
（2）這樣對數(shù)組的第 0 個數(shù)據(jù)到 N-1 個數(shù)據(jù)進(jìn)行一次遍歷后谨垃，最大的一個數(shù)據(jù)就“沉”到數(shù)組第N-1 個位置启搂。
（3）N=N-1硼控，如果 N 不為 0 就重復(fù)前面二步，否則排序完成
public static void bubbleSort(int[] a, int n) {
? ? int i, j;
? ? for (i =0; i < n; i++) {
????????for (j =1; j < n - i; j++) {
????????????if (a[j -1] > a[j]) {
????????????????int temp;
? ? ? ? ? ? ? ? temp = a[j -1];
? ? ? ? ? ? ? ? a[j -1] = a[j];
? ? ? ? ? ? ? ? a[j] = temp;
? ? ? ? ? ? }
}
}
}
插入排序算法
通過構(gòu)建有序序列胳赌，對于未排序數(shù)據(jù)牢撼，在已排序序列中從后向前掃描，找到相應(yīng)的位置并插入疑苫。插入排序非常類似于整撲克牌熏版。在開始摸牌時，左手是空的捍掺，牌面朝下放在桌上撼短。接著，一次從桌上摸起一張牌挺勿，并將它插入到左手一把牌中的正確位置上曲横。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進(jìn)行比較不瓶。無論什么時候禾嫉，左手中的牌都是排好序的。如果輸入數(shù)組已經(jīng)是排好序的話蚊丐，插入排序出現(xiàn)最佳情況夭织，其運(yùn)行時間是輸入規(guī)模的一個線性函數(shù)。如果輸入數(shù)組是逆序排列的吠撮，將出現(xiàn)最壞情況。平均情況與最壞情況一樣讲竿，其時間代價是(n2)泥兰。
public static void insertSort(int[] a) {
????for (int i =1; i < a.length; i++) {
????????int insertVal = a[i];//插入的數(shù)
? ? ? ? int index = i -1;//被插入的位置(準(zhǔn)備和前一個數(shù)比較)
? ? ? ? //如果插入的數(shù)比被插入的數(shù)小
? ? ? ? while (index >=0 && insertVal < a[index]) {
????????????//將把a(bǔ)[index]向后移動
? ? ? ? ? ? a[index +1] = a[index];
? ? ? ? ? ? //讓index向前移動
? ? ? ? ? ? index--;
? ? ? ? }
????????//把插入的數(shù)放入合適的位置
? ? ? ? a[index +1] = insertVal;
? ? }
}
快速排序算法
快速排序的原理：選擇一個關(guān)鍵值作為基準(zhǔn)值。比基準(zhǔn)值小的都在左邊序列（一般是無序的）题禀，比基準(zhǔn)值大的都在右邊（一般是無序的）鞋诗。一般選擇序列的第一個元素。一次循環(huán)：從后往前比較迈嘹，用基準(zhǔn)值和最后一個值比較削彬，如果比基準(zhǔn)值小的交換位置，如果沒有繼續(xù)比較下一個秀仲，直到找到第一個比基準(zhǔn)值小的值才交換融痛。找到這個值之后，又從前往后開始比較神僵，如果有比基準(zhǔn)值大的雁刷，交換位置，如果沒有繼續(xù)比較下一個保礼，直到找到第一個比基準(zhǔn)值大的值才交換沛励。直到從前往后的比較索引>從后往前比較的索引责语，結(jié)束第一次循環(huán)，此時目派，對于基準(zhǔn)值來說坤候，左右兩邊就是有序的了
public static void quickSort(int[] arr, int low, int high) {
????int i, j, key, t;
? ? if (low > high) {
????????return;
? ? }
????i = low;
? ? j = high;
? ? //key就是基準(zhǔn)位
? ? key = arr[low];
? ? while (i < j) {
????????//先看右邊，依次往左遞減
? ? ? ? while (key <= arr[j] && i < j) {
????????????????j--;
? ? ? ????? }
????????//再看左邊企蹭，依次往右遞增
? ? ? ? while (key >= arr[i] && i < j) {
????????????i++;
? ? ? ? }
????????//如果滿足條件則交換
? ? ? ? if (i < j) {
????????????t = arr[j];
? ? ? ? ? ? arr[j] = arr[i];
? ? ? ? ? ? arr[i] = t;
? ? ? ? }
}
????//最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
? ? arr[low] = arr[i];
? ? arr[i] = key;
? ? //此時第一次循環(huán)比較結(jié)束白筹，關(guān)鍵值的位置已經(jīng)確定了。左邊的值都比關(guān)鍵值小练对，右邊的
? ? //值都比關(guān)鍵值大遍蟋，但是兩邊的順序還有可能是不一樣的，進(jìn)行下面的遞歸調(diào)用
? ? //遞歸調(diào)用左半數(shù)組
? ? quickSort(arr, low, j -1);
? ? //遞歸調(diào)用右半數(shù)組
? ? quickSort(arr, j +1, high);
}
希爾排序算法
基本思想：先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序螟凭，待整個序列
中的記錄“基本有序”時虚青，再對全體記錄進(jìn)行依次直接插入排序。
1. 操作方法： 選擇一個增量序列 t1螺男，t2棒厘，…，tk下隧，其中 ti>tj奢人，tk=1；
2. 按增量序列個數(shù) k淆院，對序列進(jìn)行 k 趟排序何乎；
3. 每趟排序，根據(jù)對應(yīng)的增量 ti土辩，將待排序列分割成若干長度為 m 的子序列支救，分別對各子表進(jìn)行直接插入排序。僅增量因子為1 時拷淘，整個序列作為一個表來處理各墨，表長度即為整個序列的長度。
public static void shellSort(int[] a) {
????int dk = a.length /2;
? ? while (dk >=1) {
????????ShellInsertSort(a, dk);
? ? ? ? dk = dk /2;
? ? }
}
public static void ShellInsertSort(int[] a, int dk) {
//類似插入排序启涯，只是插入排序增量是 1贬堵，這里增量是 dk,把 1 換成 dk 就可以了
? ? for (int i = dk; i < a.length; i++) {
????????if (a[i] < a[i - dk]) {
????????????int j;
? ? ? ? ? ? int x = a[i];//x 為待插入元素
? ? ? ? ? ? a[i] = a[i - dk];
? ? ? ? ? ? for (j = i - dk; j >=0 && x < a[j]; j = j - dk) {
????????????????//通過循環(huán)，逐個后移一位找到要插入的位置结洼。
? ? ? ? ? ? ? ? a[j + dk] = a[j];
? ? ? ? ? ? }
????????????????a[j + dk] = x;//插入
? ? ? ? }
}
}
歸并排序算法
歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表黎做，即把待排序序列分為若干個子序列，每個子序列是有序的松忍。然后再把有序子序列合并為整體有序序列引几。
public class MergeSortTest {
????public static void main(String[] args) {
????????int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
????????print(data);
????????mergeSort(data);
????????System.out.println("排序后的數(shù)組：");
????????print(data);
}
public static void mergeSort(int[] data) {
????????sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) {
????if (left >= right)
????????return;
????// 找出中間索引
????int center = (left + right) / 2;
????// 對左邊數(shù)組進(jìn)行遞歸
????sort(data, left, center);
????// 對右邊數(shù)組進(jìn)行遞歸
????sort(data, center + 1, right);
????// 合并
????merge(data, left, center, right);
????print(data);
}
/**
* 將兩個數(shù)組進(jìn)行歸并，歸并前面 2 個數(shù)組已有序，歸并后依然有序*
* @param data 數(shù)組對象
* @param left 左數(shù)組的第一個元素的索引
* @param center 左數(shù)組的最后一個元素的索引伟桅，center+1 是右數(shù)組第一個元素的索引
* @param right 右數(shù)組最后一個元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
????// 臨時數(shù)組
????int[] tmpArr = new int[data.length];
????// 右數(shù)組第一個元素索引
????int mid = center + 1;
????// third 記錄臨時數(shù)組的索引
????int third = left;
????// 緩存左數(shù)組第一個元素的索引
????int tmp = left;
????while (left <= center && mid <= right) {
????????// 從兩個數(shù)組中取出最小的放入臨時數(shù)組
????????if (data[left] <= data[mid]) {
????????????tmpArr[third++] = data[left++];
????????} else {
????????????tmpArr[third++] = data[mid++];
????}
}
????// 剩余部分依次放入臨時數(shù)組（實(shí)際上兩個 while 只會執(zhí)行其中一個）
????while (mid <= right) {
????tmpArr[third++] = data[mid++];
????}
????while (left <= center) {
????tmpArr[third++] = data[left++];
}
// 將臨時數(shù)組中的內(nèi)容拷貝回原數(shù)組中
// （原 left-right 范圍的內(nèi)容被復(fù)制回原數(shù)組）
????while (tmp <= right) {
????????data[tmp] = tmpArr[tmp++];
????}
}
public static void print(int[] data) {
????for (int i = 0; i < data.length; i++) {
????System.out.print(data[i] + "\t");
????}
????System.out.println();
}
}
