首先總結(jié)以下Java和C社搅、C++中的一般控制臺(tái)輸入方式熬拒，方便以后的編程題：

1. java鍵盤輸入

import java.util.Scanner;
//…………
Scanner scan = new Scanner(System.in);
String s = scan.nextLine();
int a = scan.nextInt();
int b = scan.nextInt();
String s2 = scan.next();
//…………
while(scan.hasNext()){
  // 這里，循環(huán)不會(huì)隨著任何輸入而停止筋帖，除非輸入終止操作“ctrl+Z” 或“ctrl+C”等迅耘。
}

2. java讀文件（會(huì)自動(dòng)結(jié)束讀燃妗）

import java.util.Scanner;
//…………
Scanner scan;
try {
    FileInputStream fis = new FileInputStream(new File("/home/androidjp/file.txt"));//Ubuntu下的文件路徑
    scan = new Scanner(fis, "utf-8"); 
    while(scan.hasNext()){
        ///讀取里面的信息
    }
    //…………
} catch (FileNotFoundException e) {
    e.printStackTrace();
}

3. C 輸入輸出（數(shù)字和字符串监署、文件讀炔ā）

#include <stdio.h>
#include <stdlib.h>
int main(){
  freopen("D:\\file.txt", "r", stdin);//打開文件，自動(dòng)填充下面要輸入的數(shù)據(jù)钠乏。
  //..........
  scanf("%d", &a);///輸入一個(gè)整數(shù)
  scanf("%c", &ch); //輸入一個(gè)char字符
  scanf("%s" , s);///輸入一串字符（遇到空格或者換行自動(dòng)認(rèn)為輸入完畢）
  ch = getchar();//輸入一個(gè)char字符
  getchar();//一般用于接收上一行輸入完字符串后輸入的換行
  gets(s); //輸入一串字符（遇到換號(hào)才認(rèn)為輸入完畢）
  //.........
  printf("%d\n%s" , a, s);///輸入+換行
}

4. C++輸入輸出（數(shù)字和字符串）

#include <iostream>
using namespace std;
int main(){
  string s; //封裝起來的字符串
  char chs[5];//字符串（原始模樣）
  int a;
  cin >> s >> a;///輸入字符串 + 空格/換行 + 輸入數(shù)字（如果輸入了‘a(chǎn)bc def 123’栖秕，那么，s=‘a(chǎn)bc’ 晓避，a=‘0’）
  cin >> chs;
  //........
  cout << s << " , " << a << " , " << chs << endl;  ///串連起來輸出（endl為換行）
  cout << s[2];  //輸出 字符串 s 的第三個(gè)字符簇捍。
}

一只壳、字符串匹配

KMP算法

題型：大字符串（長度為n）中，是否存在子字符串（長度為m暑塑，m<=n）吼句？
KMP算法思路：利用一個(gè)O(m)的預(yù)處理，將匹配的復(fù)雜度降為O(n+m)事格。利用int[] 類型的next數(shù)組惕艳，去預(yù)處理這個(gè)需要匹配的子串，將子串中每一個(gè)元素b[i] 前面的字符串段的前綴和后綴的最大共有字符個(gè)數(shù)記錄為next[i]驹愚，這樣远搪，通過這個(gè)輔助數(shù)組next[i] ，b[j] 與 a[i]如果不匹配逢捺，那么谁鳍，就可以讓 j 回溯到next[j] ，從而讓 與后綴完全匹配的前綴的后一個(gè)元素b[新的j] 去與a[i] 進(jìn)行匹配劫瞳。

• Java實(shí)現(xiàn)：

  import java.util.Scanner;
  /**
   * KMP字符串匹配算法：實(shí)際上是根據(jù)不匹配字符位置之前的字串的前綴和后綴相同的最大長度倘潜，根據(jù)這個(gè)長度，去一次移動(dòng)子串多位柠新，以達(dá)到O(n+m)的復(fù)雜度
   * 步驟：
   * 1. 獲取子串上每一個(gè)位置之前的字符串的前后綴的最大相同長度窍荧。
   * 2. 讓大串和子串比較，每次比較途中遇到不匹配的字符恨憎，就根據(jù)“j = next[j]”去讓大串中的第i個(gè)字符與子串中第j個(gè)字符比較蕊退，模擬子串后移的過程
   * Created by androidjp on 16-8-4.
   */
  public class KMP {
    /**
     * 獲取next數(shù)組
     * @param b
     * @return
     */
    public static int[] getNext(String b){
        int j = 0;
        int len = b.length();
        int[] next = new int[len+1];
        next[0] = next[1] = 0;
        for(int i=1;i<b.length();i++){
            while(j>0 && b.charAt(i)!=b.charAt(j)) j = next[j];
            if(b.charAt(i) == b.charAt(j)) j++;
            next[i+1] = j;
        }
        return next;
    }
    public static void match(String a, String b, int[] next){
        int j = 0;
        for(int i=0;i<a.length();i++){
            while(j>0 && a.charAt(i)!=b.charAt(j)) j = next[j];
            if (a.charAt(i) == b.charAt(j)) j++;
            if (j == b.length()){
                System.out.println(i+1-j);///輸出完全匹配時(shí)i的初始位置（因?yàn)檫@時(shí)i=a.length-1, 而j=b.length ，所以i要加一）
                return;
            }
        }
        System.out.println("-1");
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String a,b;
        while(scan.hasNext()){
          a = scan.next();
          b = scan.next();
          match(a, b, getNext(b));
          }
      }
  }
  

• C 實(shí)現(xiàn)：

  ///這里憔恳，可以利用數(shù)組的第一個(gè)元素來記錄字符串的長度瓤荔，以下就是另一種寫法，但思路一致钥组。
  
  #include "stdio.h"
  #include "stdlib.h"
  #define TRUE  1
  #define FALSE  0
  #define OK  1
  #define ERROR  0
  #define INFEASLBLE  -1
  #define OVERFLOW  -2
  #define MAXSTRLEN  255    //用戶可在255以內(nèi)定義最大串長
  typedef unsigned char SString[MAXSTRLEN+1];   //0號(hào)單元存放串的長度
  void get_next(SString T,int next[])
  {
    int i=1,j=0;
    next[1]=0;
    while(i<=T[0])
        if(j==0||T[i]==T[j])
        {
            i++;
            j++;
            if(T[i]==T[j]) next[i]=next[j];
            else next[i]=j;
        }
        else j=next[j];
  }
  int Index_KMP(SString S,SString T)
  {
    int next[255];
    int i=0;
    int j=0;
    get_next(T,next);
    while(i<=S[0]&&j<=T[0])
        if(j==0||S[i]==T[j])
        {
            j++;
            i++;
        }
        else j=next[j];
    if(j>T[0]) return i-T[0];
    else return 0;
  }
  int main()
  {
    SString T,S;
    int i,j,n;
    char ch;
    int pos;
  // freopen("case.txt","r",stdin);
    scanf("%d",&n);    // 指定n對(duì)需進(jìn)行模式匹配的字符串
    ch=getchar();
    for(j=1; j<=n; j++)
    {
        ch=getchar();
        for( i=1; i<=MAXSTRLEN&&(ch!='\n'); i++)  // 錄入主串
        {
            S[i]=ch;
            ch=getchar();
        }
        S[0]=i-1;    // S[0]用于存儲(chǔ)主串中字符個(gè)數(shù)
  
        ch=getchar();
        for( i=1; i<=MAXSTRLEN&&(ch!='\n'); i++)  // 錄入模式串
        {
            T[i]=ch;
            ch=getchar();
        }
        T[0]=i-1;    // T[0]用于存儲(chǔ)模式串中字符個(gè)數(shù)
        pos=Index_KMP(S,T); 
        printf("%d\n",pos);
    }
    return 0;
  }
  

二输硝、排序

快排（QuickSort）

• 思路：改進(jìn)版的冒泡排序，采用（取基準(zhǔn)值-交換排序-遞歸）的一個(gè)過程程梦。
• 寫法：一般是三個(gè)函數(shù)：①quickSort(int[] arr) 【入口函數(shù)】 ②quickSort(int[] arr, int first, int last) 【遞歸調(diào)用函數(shù)】 ③ partition(int[] arr, int first, int last) 【獲取隨機(jī)基點(diǎn)（可以隨機(jī)点把，可以取中間）并實(shí)際交換排序過程函數(shù)】
• 時(shí)間復(fù)雜度：
  • 平均：O(nlogn)
  • 最好：O(n)
  • 最壞：O(n平方)【數(shù)組本身有序 + 每次取最后一個(gè)數(shù)字作為基準(zhǔn)】
• 空間復(fù)雜度：
  • 平均：O(logn)
  • 最好：O(logn)【n個(gè)元素，則遞歸樹的高度為logn】
  • 最壞：O(n) 【此時(shí)需要n-1次遞歸調(diào)用】
• 穩(wěn)定性：不穩(wěn)定
• Java寫法：

    /**
     * 快速排序
     */
    public static void  quickSort(int[] data) {
        quickSort(data, 0, data.length-1);
    }
    private static void quickSort(int[] data, int first,  int last) {
        if(first < last){//只要有兩個(gè)以上的元素
            int privotIndex = partition(data, first, last);
            quickSort(data, first,privotIndex-1);
            quickSort(data, privotIndex+1, last);
        }
    }
  
    private static int partition(int[] data, int first, int last) {
        int pivot = data[first];///取第一個(gè)元素為基準(zhǔn)
  //        int pivot = randomInRange(first,last);  ///或者隨機(jī)取一個(gè)元素
  //        然后與第一個(gè)元素交換
  //        int t = data[pivot];
  //        data[pivot] = data[first];
  //        data[first] = t;
        
        int low = first +1;
        int high = last;
  
        while(low < high){
            /**
             * 1. 找左側(cè)比基準(zhǔn)大的值
             */
            while(low <= high && data[low]<= pivot){
                low++;
            }
            /**
             * 2. 找右側(cè)比基準(zhǔn)小的值
             */
            while (low <= high && data[high]>pivot){
                high--;
            }
            /**
             * 3. 交換
             */
            if (low < high){
                int temp = data[low];
                data[low] = data[high];
                data[high] = temp;
            }
        }
        /***
         * 所有交換完畢后屿附，需要將這個(gè)基準(zhǔn)點(diǎn)插入到一個(gè)適當(dāng)?shù)奈恢?       */
        while(high > first && data[high]>=pivot){
            high--;
        }
        ///找到了交換點(diǎn)
        if (pivot > data[high]){
            data[first] = data[high];
            data[high] = pivot;
            return high;
        }else{///不用交換郎逃，表示這一次交換后，數(shù)組基本就是有序了
            return first;
        }
    }
  
    /**
     * 隨機(jī)取值
     */
    private static int randomInRange(int start, int end) {
        return new Random().nextInt(end-start+1)+start;
    }
  

歸并排序（MergeSort）

• 思路：利用輔助數(shù)組挺份，進(jìn)行一個(gè)“分治 - 合并” 的過程褒翰。與快排不同，快排是‘一邊分一邊執(zhí)行交換排序’，而歸并排序是‘拆分优训，進(jìn)行比較排序朵你，排了再合并’。每次拆分揣非，用到兩個(gè)部分的輔助數(shù)組抡医，每次合并，用到一個(gè)長的輔助數(shù)組早敬，所以多用了O(2N)的空間魂拦。
• 寫法：一般分兩個(gè)函數(shù)：①mergeSort(int[] arr)【遞歸分治主函數(shù)】②merge(int[] a,int[] b) 【合并函數(shù)】
• 時(shí)間復(fù)雜度：O(nlogn)
• 空間復(fù)雜度：O(n)
• 穩(wěn)定性：穩(wěn)定
• Java寫法：

    /**
     * 歸并排序
     */
    public static void mergeSort(int[] data) {
        ///遞歸條件
        if (data.length >1){
  
            /**
             * 1. 拆分兩半
             */
            int[] firstHalf = new int[data.length/2];
            System.arraycopy(data,0,firstHalf,0,firstHalf.length);
            mergeSort(firstHalf);
  
            int[] secondHalf = new int[data.length - data.length/2];
            System.arraycopy(data,data.length/2,secondHalf,0,secondHalf.length);
            mergeSort(secondHalf);
            /**
             * 2. 合并兩個(gè)部分
             */
            int[] temp = merge(firstHalf, secondHalf);
  
            /**
             * 重要：copy回原來的數(shù)組
             */
            System.arraycopy(temp, 0 , data, 0 , temp.length);
        }
    }
    ///合并
    private static int[] merge(int[] a, int[] b) {
        int[] temp = new int[a.length+ b.length];
        int i = 0;
        int j = 0;
        int k = 0;
  
        while(i<a.length && j<b.length){
            if (a[i] <b[j]){
                temp[k++]= a[i++];
            }else{
                temp[k++] = b[j++];
            }
        }
        while(i < a.length)
            temp[k++] = a[i++];
  
        while(j < b.length)
            temp[k++] = b[j++];
  
        return temp;
    }
  

冒泡排序（BubbleSort）

• 思路：從后往前移動(dòng)小元素，把小的元素移到大的元素前面搁嗓，一次遍歷至少可以移動(dòng)一個(gè)小元素上去頂端芯勘。相鄰元素之間的比較和交換，第一遍：從len-1 到0腺逛， 第二遍：從len-1 到1 荷愕，……
• 平均/最差時(shí)間復(fù)雜度：O(n平方)
• 最好時(shí)間復(fù)雜度：O(n)【從arr[len-1] 到arr[0] 的過程沒有一次交換】
• 穩(wěn)定性：穩(wěn)定
• Java寫法：

    /**
     * 冒泡排序
     * 相鄰元素比較和交換的過程
     * 1. 從len-1 到 0
     * 2. 從len-1 到 1
     * 3. 從len-1 到 2
     * …………
     */
    private static void bubbleSort(int[] data) {
        if (data== null|| data.length==0){
            throw  new RuntimeException("參數(shù)無效");
        }
        for (int i=0;i<data.length-1;i++){
            boolean isSwap = false;
            for(int j=data.length-1;j>i;j--){
                if (data[j] < data[j-1]){
                    //交換
                    int temp = data[j-1];
                    data[j-1] =data[j];
                    data[j] = temp;
                    ///設(shè)置為“需要交換”
                    isSwap = true;
                }
            }
            if (!isSwap)
                return;
        }
    }
  

直接選擇排序（SelectSort）

• 思路：每次從前往后查找，選擇亂序中最小的元素棍矛，放到上面來安疗。
• 時(shí)間復(fù)雜度：O(n平方)【只適用于從大量元素中選擇一部分排序元素，例如從1w個(gè)元素中找出前10個(gè)元素】
• 穩(wěn)定性：不穩(wěn)定
• Java寫法：

    public static void selectSort(int[] data){
        if (data == null || data.length <= 0)
            throw new RuntimeException("Invalid Paramemers");
        ////每次從前到后選擇最小的元素够委，把它交換上來
        for(int i=0;i<data.length-1;i++){
            int minIndex  = i;
            for(int j = i+1;j<data.length;j++){
                if (data[j] < data[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                //交換
                int temp = data[minIndex];
                data[minIndex] =data[i];
                data[i] = temp;
            }
        }
    }
  

堆排序（HeapSort）

• 思路：一種樹形選擇排序算法荐类。排序過程中將data[1…n]當(dāng)做一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和子結(jié)點(diǎn)之間的內(nèi)在關(guān)系茁帽，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最杏窆蕖）的元素。
• 時(shí)間復(fù)雜度：O(nlogn)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定
• 分析：由于建初始堆所需的比較次數(shù)較多潘拨，所以堆排序不適宜于記錄數(shù)較少的文件吊输。
• Java寫法：

    /**
     * 堆排
     * @param data
     */
    public static void heapSort(int[] data, int len){
        if(data==null || len<=0)
            throw new RuntimeException("invalid parameters");
        /**
         * 1. 初始化堆（從最小個(gè)的堆開始整理，慢慢整理到最大個(gè)的堆）
         */
        for(int i=len/2;i>=1;i--){//從最后一個(gè)擁有子結(jié)點(diǎn)的結(jié)點(diǎn)開始往上循環(huán)調(diào)整堆
            initHeap(data, i,len);
        }
  
        System.out.println(data[1]);
  
        /**
         * 2. 一個(gè)個(gè)堆頂?shù)闹档妮敵鎏罚⒅匦抡{(diào)整堆的過程
         */
        for(int i=len;i>=2;i--){
            //首先季蚂，將堆頂元素與數(shù)組末尾的元素?fù)Q位置，然后琅束，數(shù)組整理堆調(diào)整長度-1
            int temp = data[i];
            data[i] = data[1];
            data[1] = temp;
            System.out.println("這次換位之后扭屁，末尾的值是："+ data[i]);
            initHeap(data, 1,i-1);
        }
    }
    //構(gòu)造大頂堆的過程
    private static void initHeap(int[] data, int low, int high) {
        int i = low;
        int j = i*2;
        int temp = data[i];
        while(j<=high){
            if (j<high && data[j]<data[j+1]) j++;
            if (temp < data[j]){
                data[i] = data[j];
                i = j;
                j = 2*i;
            }else
                break;
        }
        data[i] = temp;//從后往前賦值
    }
  

直接插入排序（InsertSort）

• 思路：將數(shù)組中第二個(gè)元素開始，每個(gè)元素都慢慢往前查找最適合插入的點(diǎn)涩禀，然后插入（讓前面的元素一一后移一位料滥，讓出位置給其插入。
• 平均/最差時(shí)間復(fù)雜度：O(n平方)
• 最好事件復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：穩(wěn)定
• Java寫法：

  private static int[] insertSort(int[] data, int len) {
    if(data != null && len > 0) {
        for(int i = 1; i < len; ++i) {  ///從第二個(gè)元素開始
            int temp = data[i];
            int j;
            for(j = i - 1; j >= 0 && data[j] >= temp; --j) { ///尋找適合的插入位置
                data[j + 1] = data[j];///慢慢讓前面的元素后移埋泵，騰出位置
            }
            data[j + 1] = temp; ///最后插入
        }
        return data;   ///最終輸出排好序的數(shù)組
    }else {
        throw new RuntimeException("參數(shù)無效");
    }
  }
  

希爾排序（ShellSort）

• 思路：用一個(gè)間隔參數(shù)（也可以說是增量）d幔欧， 去將原來插入排序的一一后移 1 步，變成 一一后移 d 步丽声，比如：d = 2礁蔗，那么，整個(gè)數(shù)組拆分成兩組：{a[0],a[2],a[4]}和{a[1],a[3],a[5]}雁社，然后組內(nèi)比較浴井，實(shí)際上就是間隔著去移位和插入【實(shí)際上，如果數(shù)組一開始就是有序的霉撵，那么Shell和Insert兩種排序所需要的比較次數(shù)和移動(dòng)次數(shù)都會(huì)很少磺浙。】

  • n 比較型狡隆：InsertSort的最好和最壞時(shí)間復(fù)雜度O(n)和O(n平方)差別不大
  • n 比較大：InsertSort的最壞事件復(fù)雜度則效率較低撕氧，而這時(shí)，由于一個(gè)d的存在喇完，首先就把一部分本來需要的插入移位操作給做了伦泥，所以，這時(shí)锦溪，當(dāng)gap以除以2的速度減小時(shí)不脯，這一整趟排序整體需要的比較次數(shù)和移位次數(shù)就少了，于是效率高了刻诊。

• 平均時(shí)間復(fù)雜度：O(n^1.3)

• 空間復(fù)雜度：O(1)

• 穩(wěn)定性：不穩(wěn)定（因?yàn)槊看巍纸M’之后防楷，原來排在前面的‘1’，可能變成排到后面去了）

• Java寫法：

    private static int[] shellSort(int[] data, int len) {
        int d = len/2;
        while(d > 0){
            for(int i=d; i< len; i++){
                int temp = data[i];//取第len/2個(gè)元素（數(shù)組后半段）拿這個(gè)元素和前一組的所有元素進(jìn)行比較则涯，看到適當(dāng)?shù)奈恢镁筒迦?              int j = i - d;
                while(j >=0 && temp < data[j]){///每次需要騰出位置時(shí)复局，不是移動(dòng)一個(gè)位置，而是移動(dòng)d個(gè)位置
                    data[j+d] = data[j];
                    j -=d;
                }
                data[j+d] = temp;
            }
            d /=2;
        }
        return data;
    }
  

基數(shù)排序（RadixSort）

• 思路：將數(shù)組中每一個(gè)元素按：個(gè)位粟判、十位肖揣、百位、……的順序取一個(gè)自然數(shù)出來浮入，然后對(duì)他們進(jìn)行比較和排序龙优。在排序過程中類似于HashMap的那種數(shù)組加鏈表的結(jié)構(gòu)，所以需要一個(gè)輔助類Node事秀，表示一個(gè)鏈表結(jié)點(diǎn)彤断，只是這個(gè)數(shù)組只有0~9這幾個(gè)元素。
• 平均/最好/最差時(shí)間復(fù)雜度：O(nlog(r)m)【r表示采用的基數(shù)易迹，m表示堆數(shù)】
• 空間復(fù)雜度：O(r)
• 穩(wěn)定性：穩(wěn)定
• Java寫法：

    /**
     * 基數(shù)排序（桶排序）宰衙，某些時(shí)候，效率會(huì)高一點(diǎn)
     * 效率與：進(jìn)制 睹欲、位數(shù) 供炼、數(shù)組元素個(gè)數(shù) 一屋、元素的最高位數(shù)   有關(guān)
     */
    private static int[] radixSort(int[] data, int len, int jinzhi, int weishu) {
  
        if (data == null || len <= 0 || jinzhi <= 0 || weishu < 1)
            throw new RuntimeException("Invalid Parameters");
        
        ///這里就需要將這個(gè)數(shù)組中所有元素都變成一個(gè)Node類
        class Node {
            int num;
            Node next;
        }
  
        Node myHead = new Node();
        myHead.next = null;
        Node myTail = myHead;
  
        ///數(shù)組 轉(zhuǎn) 鏈表
        for (int i = 0; i < len; i++) {
            Node item = new Node();
            item.num = data[i];
            item.next = null;
            myTail.next = item;
            myTail = item;
        }
  
        ///===========================================
  
        Node[] heads = new Node[jinzhi];
        Node[] tails = new Node[jinzhi];
  
        Node tempHead = null;
  
        for (int i = 0; i < weishu; i++) {
            /**
             * 1. 首先，初始化大數(shù)組
             */
            for (int j = 0; j < jinzhi; j++) {
                heads[j] = null;
                tails[j] = null;
            }
            tempHead = myHead;
            /**
             * 2. 然后袋哼，放桶
             */
            while (tempHead.next != null) {//證明有數(shù)組
                tempHead = tempHead.next;
                int k = getDigit(tempHead.num, i);
                if (heads[k] == null) {///直接數(shù)組頭就開始存放元素冀墨，這樣就少了(進(jìn)制)個(gè)Node空間
                    heads[k] = tempHead;
                    tails[k] = heads[k];
                } else {
                    tails[k].next = tempHead;
                    tails[k] = tails[k].next;
                }
            }
            /**
             * 3. 重新 連成鏈表
             */
            myHead.next = null;
            myTail = myHead;
            ///注意，取出每一個(gè)小鏈表來構(gòu)建大鏈表的過程中：
            for (int j = 0; j < jinzhi; j++) {
                if (heads[j] !=null){
                    if (myHead.next == null){
                        myHead.next = heads[j];
                    }else{
                        //注意這里涛贯，當(dāng)大鏈表不為空的情況诽嘉，記得修復(fù)好myTail.next去連接
                        myTail.next = heads[j];
                    }
                    myTail = tails[j];
                }
            }
            myTail.next = null;
            tempHead = null;
        }
        /**
         * 4. 最終，重新：鏈表 轉(zhuǎn) 數(shù)組
         */
        myTail = myHead;
        int k = 0;
        while (myTail.next != null) {
            myTail = myTail.next;
            data[k++] = myTail.num;
        }
        //返回?cái)?shù)組
        return data;
    }
  
    public static int getDigit(int x, int d) {
        int a[] = {1, 10, 100, 1000, 10000}; // 如果實(shí)例的最大數(shù)是百位數(shù)弟翘，那就只要到100就可以了
        return ((x / a[d]) % 10);
    }
  

三虫腋、查找

二分查找

• 平均/最差時(shí)間復(fù)雜度：O(logn)
• 平均查找長度ASL：log(n+1) - 1
• 空間復(fù)雜度：O(1)
• 前提要求：線性表是有序的。
• 適用情況：為保持順序表的有序稀余，表的插入和刪除操作都需要移動(dòng)大量元素悦冀，所以折半查找特別適用于一旦建立就很少改動(dòng)，又經(jīng)常需要進(jìn)行查找的線性表睛琳。
• Java寫法：

    public static int BinarySearch(int[] data, int len, int key){
        if (data == null || len <=0)
            throw new RuntimeException("invalid parameters");
        int low = 0;
        int high = len -1;
        while(low <= high){
            int mid = (low + high)/2;
            if(data[mid] == key)
                return mid;
            else if (data[mid]< key)
                low = mid+1;
            else
                high = mid-1;
        }
        return -1;
    }
  

四雏门、內(nèi)排序方法的比較和總結(jié)

補(bǔ)充說明：
關(guān)于基數(shù)排序的平均時(shí)間復(fù)雜度、最差時(shí)間復(fù)雜度和空間復(fù)雜度掸掏，可以如下理解：

1. 排序分類（按時(shí)間復(fù)雜度）：

• 平方階O(n^2)排序茁影，一般稱為簡單排序，例如直接插入排序丧凤，直接選擇排序和冒泡排序
• 線性對(duì)數(shù)階O(nlogn)排序募闲，如快速排序、堆排序和歸并排序
• 線性階O(n)排序愿待，如基數(shù)排序（假定數(shù)據(jù)的位數(shù)d和進(jìn)制r為常量時(shí)）

2. 使用結(jié)論
3. 若n較泻坡荨（如n<=50），可采用直接插入排序或直接選擇排序仍侥。當(dāng)元素規(guī)模較小時(shí)要出，直接插入排序較好；否則因?yàn)橹苯舆x擇排序移動(dòng)的元素少于直接插入排序农渊，應(yīng)選直接選擇排序患蹂。
4. 若文件初始狀態(tài)基本有序（指正序），則應(yīng)選用直接插入砸紊、冒泡或隨機(jī)的快速排序传于。
5. 若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlogn)的排序方法：快速排序醉顽、堆排序或歸并排序沼溜。快速排序被認(rèn)為是目前基于比較的內(nèi)部排序中較好的方法游添，當(dāng)待排序的關(guān)鍵字隨機(jī)分布時(shí)系草，快速排序的平均時(shí)間最短通熄；但堆排序所需的輔助空間比快速排序少，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況找都。這兩種排序都是不穩(wěn)定的唇辨，若要求穩(wěn)定，則可選用歸并排序檐嚣。
6. 若要將兩個(gè)有序表合并成一個(gè)新的有序表，最好的方法是歸并排序啰扛。
7. 在基于比較的排序方法中嚎京，至少是需要O(nlogn)的時(shí)間。而基數(shù)排序只需要一步就會(huì)引起r種可能的轉(zhuǎn)移隐解，即把一個(gè)元素裝入r個(gè)隊(duì)列之一鞍帝，因此一般情況下，基數(shù)排序可能在O(n)時(shí)間內(nèi)完成對(duì)n個(gè)元素的排序煞茫。但遺憾的是帕涌，基數(shù)排序只適用于像字符串和整數(shù)這類有明顯結(jié)構(gòu)特征的關(guān)鍵字，而當(dāng)關(guān)鍵字的取值范圍屬于某個(gè)無窮集合（例如實(shí)數(shù)型關(guān)鍵字）時(shí)续徽，無法使用基數(shù)排序蚓曼，這時(shí)只有借助于“比較”的方法來排序。由此可知钦扭，若n很大纫版，元素的關(guān)鍵字位數(shù)較少且可以分解時(shí)，采用基數(shù)排序較好客情。

參考文章：
http://www.reibang.com/p/3471b2dfa2b4#