二分查找

又叫折半查找，要求待查找的序列有序。每次取中間位置的值與待查關鍵字比較，如果中間位置的值比待查關鍵字大，則在前半部分循環這個查找的過程，如果中間位置的值比待查關鍵字小，則在后半部分循環這個查找的過程。直到查找到了為止，否則序列中沒有待查的關鍵字。

 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+1;
 }else if(array[mid]<a){ //向右查找
lo=mid+1;
 }else{ //向左查找
hi=mid-1;
 }
 }
 return -1;
 }

冒泡排序算法

（1）比較前后相鄰的二個數據，如果前面數據大于后面的數據，就將這二個數據交換。

（2）這樣對數組的第 0 個數據到 N-1 個數據進行一次遍歷后，最大的一個數據就“沉”到數組第N-1 個位置。

（3）N=N-1，如果 N 不為 0 就重復前面二步，否則排序完成。

 public static void bubbleSort1(int [] a, int n){
 int i, j;
for(i=0; i<n; i++){//表示 n 次排序過程。
 for(j=1; j<n-i; j++){
 if(a[j-1] > a[j]){//前面的數字大于后面的數字就交換
//交換 a[j-1]和 a[j]
 int temp;
 temp = a[j-1];
 a[j-1] = a[j];
 a[j]=temp;
 }
 }
 }
}

插入排序算法

通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應的位置并插入。

插入排序非常類似于整撲克牌。在開始摸牌時，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進行比較。無論什么時候，左手中的牌都是排好序的。

如果輸入數組已經是排好序的話，插入排序出現最佳情況，其運行時間是輸入規模的一個線性函數。如果輸入數組是逆序排列的，將出現最壞情況。平均情況與最壞情況一樣，其時間代價是(n2)。

public void sort(int arr[])
{
 for(int i =1; i<arr.length;i++)
 {
//插入的數
 int insertVal = arr[i];
//被插入的位置(準備和前一個數比較)
 int index = i-1;
//如果插入的數比被插入的數小
 while(index>=0&&insertVal<arr[index])
 {
//將把 arr[index] 向后移動
 arr[index+1]=arr[index];
//讓 index 向前移動
 index--;
 }
//把插入的數放入合適位置
 arr[index+1]=insertVal;
 }
 }

快速排序算法

快速排序的原理：選擇一個關鍵值作為基準值。比基準值小的都在左邊序列（一般是無序的），比基準值大的都在右邊（一般是無序的）。一般選擇序列的第一個元素。

一次循環：從后往前比較，用基準值和最后一個值比較，如果比基準值小的交換位置，如果沒有繼續比較下一個，直到找到第一個比基準值小的值才交換。找到這個值之后，又從前往后開始比較，如果有比基準值大的，交換位置，如果沒有繼續比較下一個，直到找到第一個比基準值大的值才交換。直到從前往后的比較索引>從后往前比較的索引，結束第一次循環，此時，對于基準值來說，左右兩邊就是有序的了。

 public void sort(int[] a,int low,int high){
 int start = low;
 int end = high;
int key = a[low];
 while(end>start){
//從后往前比較
 while(end>start&&a[end]>=key)
//如果沒有比關鍵值小的，比較下一個，直到有比關鍵值小的交換位置，然后又從前往后比較
 end--;
 if(a[end]<=key){
 int temp = a[end];
 a[end] = a[start];
 a[start] = temp;
 }
//從前往后比較
 while(end>start&&a[start]<=key)
//如果沒有比關鍵值大的，比較下一個，直到有比關鍵值大的交換位置
 start++;
 if(a[start]>=key){
 int temp = a[start];
 a[start] = a[end];
 a[end] = temp;
 }
 //此時第一次循環比較結束，關鍵值的位置已經確定了。左邊的值都比關鍵值小，右邊的
值都比關鍵值大，但是兩邊的順序還有可能是不一樣的，進行下面的遞歸調用
 }
//遞歸
 if(start>low) sort(a,low,start-1);//左邊序列。第一個索引位置到關鍵值索引-1
 if(end<high) sort(a,end+1,high);//右邊序列。從關鍵值索引+1 到最后一個
 }
 }

希爾排序算法

基本思想：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

1. 操作方法：

選擇一個增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；

2. 按增量序列個數 k，對序列進行 k 趟排序；

3. 每趟排序，根據對應的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

private void shellSort(int[] a) {
int dk = a.length/2;
while( dk >= 1 ){
 ShellInsertSort(a, dk);
 dk = dk/2;
}
}
private 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){
//通過循環，逐個后移一位找到要插入的位置。
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("排序后的數組：");
 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;
 // 對左邊數組進行遞歸
 sort(data, left, center);
 // 對右邊數組進行遞歸
 sort(data, center + 1, right);
 // 合并
 merge(data, left, center, right);
 print(data);
 }
 /**
 * 將兩個數組進行歸并，歸并前面 2 個數組已有序，歸并后依然有序
*
 * @param data
 * 數組對象
 * @param left
 * 左數組的第一個元素的索引
 * @param center
 * 左數組的最后一個元素的索引，center+1 是右數組第一個元素的索引
 * @param right
 * 右數組最后一個元素的索引
 */
 public static void merge(int[] data, int left, int center, int right) {
 // 臨時數組
 int[] tmpArr = new int[data.length];
 // 右數組第一個元素索引
 int mid = center + 1;
 // third 記錄臨時數組的索引
 int third = left;
 // 緩存左數組第一個元素的索引
 int tmp = left;
 while (left <= center && mid <= right) {
 // 從兩個數組中取出最小的放入臨時數組
 if (data[left] <= data[mid]) {
 tmpArr[third++] = data[left++];
 } else {
 tmpArr[third++] = data[mid++];
 }
 }
 // 剩余部分依次放入臨時數組（實際上兩個 while 只會執行其中一個）
 while (mid <= right) {
 tmpArr[third++] = data[mid++];
}
 while (left <= center) {
 tmpArr[third++] = data[left++];
 }
 // 將臨時數組中的內容拷貝回原數組中
 // （原 left-right 范圍的內容被復制回原數組）
 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();
 }
 }

桶排序算法

桶排序的基本思想是： 把數組 arr 劃分為 n 個大小相同子區間（桶），每個子區間各自排序，最后合并 。計數排序是桶排序的一種特殊情況，可以把計數排序當成每個桶里只有一個元素的情況。

1.找出待排序數組中的最大值 max、最小值 min

2.我們使用 動態數組 ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲。桶的數量為(maxmin)/arr.length+1

3.遍歷數組 arr，計算每個元素 arr[i] 放的桶

4.每個桶各自排序

public static void bucketSort(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//創建桶
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
//將每個元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//對每個桶進行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
}

基數排序算法

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后,數列就變成一個有序序列。

public class radixSort {
inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,2
5,53,51};
public radixSort(){
sort(a);
for(inti=0;i<a.length;i++){
System.out.println(a[i]);
}
}
public void sort(int[] array){
//首先確定排序的趟數;
int max=array[0];
for(inti=1;i<array.length;i++){
if(array[i]>max){
max=array[i];
}
}
int time=0;
//判斷位數;
while(max>0){
max/=10;
time++;
}
//建立 10 個隊列;
List<ArrayList> queue=newArrayList<ArrayList>();
for(int i=0;i<10;i++){
ArrayList<Integer>queue1=new ArrayList<Integer>();
queue.add(queue1);
}
//進行 time 次分配和收集;
for(int i=0;i<time;i++){
//分配數組元素;
for(intj=0;j<array.length;j++){
//得到數字的第 time+1 位數;
int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
ArrayList<Integer>queue2=queue.get(x);
queue2.add(array[j]);
queue.set(x, queue2);
}
int count=0;//元素計數器;
//收集隊列元素;
for(int k=0;k<10;k++){
while(queue.get(k).size()>0){
ArrayList<Integer>queue3=queue.get(k);
array[count]=queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
}

剪枝算法

在搜索算法中優化中，剪枝，就是通過某種判斷，避免一些不必要的遍歷過程，形象的說，就是剪去了搜索樹中的某些“枝條”，故稱剪枝。應用剪枝優化的核心問題是設計剪枝判斷方法，即確定哪些枝條應當舍棄，哪些枝條應當保留的方法。

回溯算法

回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”返回，嘗試別的路徑。

最短路徑算法

從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA算法等。

最大子數組算法
題目：輸入一個整形數組，數組里有正數也有負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。

求所有子數組的和的最大值。要求時間復雜度為O(n)。比如輸入a[]={31,-41,59,26,-53,58,97,-93,-23,84}，那么程序的輸出為a[2...6]的和，即187。

《編程珠璣》給出了一個時間復雜度為O(n)的掃描算法。代碼非常簡練，但得稍微思考一下才能明白。

首先我們必須找到最大的子數組的起始點，從a[0]開始掃描，并且逐一累加，累加和存儲到max_ending_here變量。當累加到i,即a[0]+a[1]+...a[i]的和小于0時，我們認定最大子數組絕對不包括a[0]~a[i],就可以更新最大子數組的起始位置begin=i+1，并將max_ending_here清0。所以說max_ending_here始終存儲的是累加和大于0的子數組累加和。這時還需要另外一個變量max_sofar存儲當前的最大子數組累加和。每掃描一個數據就將max_ending_here和max_sofar進行一次比較，保證max_sofar始終存儲目前最大的子數組累加和。代碼如下：

#include "stdafx.h"
#include "stdio.h"
#include <IOStream>
using namespace std;
 
int max_subarray(const int a[],int n)
{
	int max_ending_here=0;
	int max_sofar=0;
	int begin=0;
	int end=0;
	int i=0;
	for(i=0;i<n;i++)
	{
		if(max_ending_here+a[i]>0)
		   max_ending_here=max_ending_here+a[i];
		else
		{
			begin=i+1; //注意begin更新為i+1而不是i
			max_ending_here=0;
		}
		cout<<"max_ending_here: "<<max_ending_here<<endl;
 
		if(max_ending_here>max_sofar)
		{
			max_sofar=max_ending_here;
			end=i;
		}
 
		cout<<"max_sofar: "<<max_sofar<<endl;
	}
	cout<<"max subarray begin="<<begin<<" "<<"end="<<end<<endl;
	return max_sofar;
}
 
int _tmain(int argc, _TCHAR* argv[])
 
{
	int sum;
	int a[]={31,-41,59,26,-53,58,97,-93,-23,84};
    sum= max_subarray(a,10);
	cout<<sum<<endl;
   getchar();
	
}

 最長公共子序算法
/* 
* 最長公共子序列算法。 
*/ 
public class LCS {
public static void main(String[] args) {
    // TODO Auto-generated method stub
    String arr1="abcdefghijk";
    String arr2="adefabcdk";
    String subMax="";
    subMax=get_LCS_sub(arr1,arr2);
    System.out.println("LCS..."+subMax);
}
private static String get_LCS_sub(String arr1, String arr2) {
    // TODO Auto-generated method stub
    String sub="";
    int ti,tj;
    int max=0;
    int rs=0,re=0;//記錄最長子串在arr1中的開始和結束位置。
    for(int i=0;i<arr1.length();){
        ti=i;//記錄i當前位置。
        for(int j=0;j<arr2.length();){
            tj=j;//記錄j當前位置。
            while(i<arr1.length()&&j<arr2.length()&&arr1.charAt(i)==arr2.charAt(j)){
                i++;
                j++;
            }
            j=tj+1;
            if((i-ti)>max){
                max=i-ti;//記錄最長子串。
                rs=ti;
                re=i;
            }
        }
        i=ti+1;
    }
    sub=arr1.substring(rs, re);
    return sub;
}

最小生成樹算法

現在假設有一個很實際的問題：我們要在 n 個城市中建立一個通信網絡，則連通這 n 個城市需要布置 n-1 一條通信線路，這個時候我們需要考慮如何在成本最低的情況下建立這個通信網？

于是我們就可以引入連通圖來解決我們遇到的問題，n 個城市就是圖上的 n 個頂點，然后，邊表示兩個城市的通信線路，每條邊上的權重就是我們搭建這條線路所需要的成本，所以現在我們有 n 個頂點的連通網可以建立不同的生成樹，每一顆生成樹都可以作為一個通信網，當我們構造這個連通網所花的成本最小時，搭建該連通網的生成樹，就稱為最小生成樹。

構造最小生成樹有很多算法，但是他們都是利用了最小生成樹的同一種性質：MST 性質（假設N=(V,{E})是一個連通網，U 是頂點集 V 的一個非空子集，如果（u，v）是一條具有最小權值的邊，其中 u 屬于 U，v 屬于 V-U，則必定存在一顆包含邊（u，v）的最小生成樹），下面就介紹兩種使用 MST 性質生成最小生成樹的算法：普里姆算法和克魯斯卡爾算法。