作者丨淺羽Eric

來源丨淺羽的IT小屋

對(duì)于編程來說的話，只有掌握了算法才是了解了編程的靈魂，算法對(duì)于新手來說的話，屬實(shí)有點(diǎn)難度，但是以后想有更好的發(fā)展，得到更好的進(jìn)階的話，對(duì)算法進(jìn)行系統(tǒng)的學(xué)習(xí)是重中之重的。

對(duì)于 Java 程序員來說，這一門后端語言只是我們的外功，我們更多的是學(xué)習(xí)它的語法，框架以及一些工具的使用。而算法才是我們真正的內(nèi)功，它更多的是關(guān)注如何設(shè)計(jì)系統(tǒng)，如何編寫高性能的代碼，不斷培養(yǎng)我們的思維能力，從而提升我們的工作效率。

小羽今天為大家介紹的是關(guān)于 Java 中我們需要了解的一些經(jīng)典算法，希望大家能從這些經(jīng)典算法中，品嘗到算法的美妙與奇特，對(duì)她產(chǎn)生興趣，更好的為我們的職業(yè)發(fā)展助力前行。好了，開始進(jìn)入我們的正文：

二分查找

簡(jiǎn)介

基本思想：又叫折半查找，要求待查找的序列有序，是一種快速查找算法，時(shí)間復(fù)雜度為 O(logn)，要求數(shù)據(jù)集為一個(gè)有序數(shù)據(jù)集。

使用

應(yīng)用場(chǎng)景：一般用于查找數(shù)組元素，并且數(shù)組在查找之前必須已經(jīng)排好序（一般是升序）。

步驟：

1、取中間位置的值與待查關(guān)鍵字比較，如果中間位置的值比待查關(guān)鍵字大，則在前半部分循環(huán)這個(gè)查找的過程，

2、如果中間位置的值比待查關(guān)鍵字小，則在后半部分循環(huán)這個(gè)查找的過程。

3、直到查找到了為止，否則序列中沒有待查的關(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+1;
        }else if(array[mid]<a){ //向右查找
            lo=mid+1;
        }else{ //向左查找
            hi=mid-1;
        } 
  }
    return -1;
}

冒泡排序算法

簡(jiǎn)介

基本思想：比較前后相鄰的兩個(gè)數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將這二個(gè)數(shù)據(jù)交換。這樣對(duì)數(shù)組的第 0 個(gè)數(shù)據(jù)到 N-1 個(gè)數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個(gè)數(shù)據(jù)就“沉”到數(shù)組第 N-1 個(gè)位置。N=N-1，如果 N 不為 0 就重復(fù)前面二步，否則排序完成。

使用

應(yīng)用場(chǎng)景：數(shù)據(jù)量不大，對(duì)穩(wěn)定性有要求，且數(shù)據(jù)基本有序的情況。

步驟：

1、將序列中所有元素兩兩比較，將最大的放在最后面。

2、將剩余序列中所有元素兩兩比較，將最大的放在最后面。

3、重復(fù)第二步，直到只剩下一個(gè)數(shù)。

代碼示例：

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]){//前面的數(shù)字大于后面的數(shù)字就交換
                //交換 a[j-1]和 a[j]
                int temp;
                temp = a[j-1];
                a[j-1] = a[j];
                a[j]=temp;
            } 
    }
  }
}

插入排序算法

簡(jiǎn)介

基本思想：通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)的位置并插入。

使用

應(yīng)用場(chǎng)景：數(shù)據(jù)量不大，對(duì)算法的穩(wěn)定性有要求，且數(shù)據(jù)局部或者整體有序的情況。

步驟：

1、將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。

2、從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）

代碼示例：

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 對(duì) arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 從下標(biāo)為1的元素開始選擇合適的位置插入，因?yàn)橄聵?biāo)為0的只有一個(gè)元素，默認(rèn)是有序的
        for (int i = 1; i < arr.length; i++) {

            // 記錄要插入的數(shù)據(jù)
            int tmp = arr[i];

            // 從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的數(shù)，插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}

快速排序算法

簡(jiǎn)介

基本思想：選擇一個(gè)關(guān)鍵值作為基準(zhǔn)值。比基準(zhǔn)值小的都在左邊序列（一般是無序的），比基準(zhǔn)值大的都在右邊（一般是無序的）。一般選擇序列的第一個(gè)元素。

使用

應(yīng)用場(chǎng)景：數(shù)值范圍較大，相同值的概率較小，數(shù)據(jù)量大且不考慮穩(wěn)定性的情況，數(shù)值遠(yuǎn)大于數(shù)據(jù)量時(shí)威力更大。

步驟：

1、一次循環(huán)，從后往前比較，用基準(zhǔn)值和最后一個(gè)值比較，如果比基準(zhǔn)值小的交換位置，如果沒有繼續(xù)比較下一個(gè)，直到找到第一個(gè)比基準(zhǔn)值小的值才交換。

2、找到這個(gè)值之后，又從前往后開始比較，如果有比基準(zhǔn)值大的，交換位置，如果沒有繼續(xù)比較下一個(gè)，直到找到第一個(gè)比基準(zhǔn)值大的值才交換。

3、直到從前往后的比較索引 > 從后往前比較的索引，結(jié)束第一次循環(huán)，此時(shí)，對(duì)于基準(zhǔn)值來說，左右兩邊就是有序的了。

代碼示例：

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) 
                //如果沒有比關(guān)鍵值小的，比較下一個(gè)，直到有比關(guān)鍵值小的交換位置，然后又從前往后比較
                end--;
            if(a[end]<=key){
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            //從前往后比較
            while(end>start&&a[start]<=key)
                //如果沒有比關(guān)鍵值大的，比較下一個(gè)，直到有比關(guān)鍵值大的交換位置
                start++;
            if(a[start]>=key){
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        //此時(shí)第一次循環(huán)比較結(jié)束，關(guān)鍵值的位置已經(jīng)確定了。左邊的值都比關(guān)鍵值小，右邊的值都比關(guān)鍵值大，但是兩邊的順序還有可能是不一樣的，進(jìn)行下面的遞歸調(diào)用
        }
        //遞歸
        if(start>low) sort(a,low,start-1);//左邊序列。第一個(gè)索引位置到關(guān)鍵值索引-1
        if(end<high) sort(a,end+1,high);//右邊序列。從關(guān)鍵值索引+1 到最后一個(gè)
    }
}

希爾排序算法

簡(jiǎn)介

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

使用

應(yīng)用場(chǎng)景：數(shù)據(jù)量較大，不要求穩(wěn)定性的情況。

步驟：

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

2、按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；

3、每趟排序，根據(jù)對(duì)應(yīng)的增量 ti，將待排序列分割成若干長(zhǎng)度為 m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。

代碼示例：

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){
                //通過循環(huán)，逐個(gè)后移一位找到要插入的位置。
                a[j+dk]=a[j];
            }
            a[j+dk]=x;//插入
        }
  }
}

歸并排序算法

簡(jiǎn)介

基本思想：歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

場(chǎng)景使用

應(yīng)用場(chǎng)景：內(nèi)存少的時(shí)候使用，可以進(jìn)行并行計(jì)算的時(shí)候使用。

步驟：

1、選擇相鄰兩個(gè)數(shù)組成一個(gè)有序序列。

2、選擇相鄰的兩個(gè)有序序列組成一個(gè)有序序列。

3、重復(fù)第二步，直到全部組成一個(gè)有序序列。

代碼示例：

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; 
        // 對(duì)左邊數(shù)組進(jìn)行遞歸
        sort(data, left, center); 
        // 對(duì)右邊數(shù)組進(jìn)行遞歸
        sort(data, center + 1, right); 
        // 合并
        merge(data, left, center, right); 
        print(data); 
    } 

    /** 
    * 將兩個(gè)數(shù)組進(jìn)行歸并，歸并前面 2 個(gè)數(shù)組已有序，歸并后依然有序
    * @param data 
    * 數(shù)組對(duì)象
    * @param left 
    * 左數(shù)組的第一個(gè)元素的索引
    * @param center 
    * 左數(shù)組的最后一個(gè)元素的索引，center+1 是右數(shù)組第一個(gè)元素的索引
    * @param right 
    * 右數(shù)組最后一個(gè)元素的索引
    */ 
    public static void merge(int[] data, int left, int center, int right) { 
        // 臨時(shí)數(shù)組
        int[] tmpArr = new int[data.length]; 
        // 右數(shù)組第一個(gè)元素索引
        int mid = center + 1; 
        // third 記錄臨時(shí)數(shù)組的索引
        int third = left; 
        // 緩存左數(shù)組第一個(gè)元素的索引
        int tmp = left; 
        while (left <= center && mid <= right) { 
            // 從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組
            if (data[left] <= data[mid]) { 
                tmpArr[third++] = data[left++]; 
            } else { 
                tmpArr[third++] = data[mid++]; 
            } 
        } 
        // 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè) while 只會(huì)執(zhí)行其中一個(gè)）
        while (mid <= right) { 
            tmpArr[third++] = data[mid++]; 
        } 
        while (left <= center) { 
            tmpArr[third++] = data[left++]; 
        } 
        // 將臨時(shí)數(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(); 
    } 
}

桶排序算法

簡(jiǎn)介

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

使用

應(yīng)用場(chǎng)景：在數(shù)據(jù)量非常大，而空間相對(duì)充裕的時(shí)候是很實(shí)用的，可以大大降低算法的運(yùn)算數(shù)量級(jí)。

步驟：

1、找出待排序數(shù)組中的最大值 max、最小值 min

2、我們使用動(dòng)態(tài)數(shù)組 ArrayList 作為桶，桶里放的元素也用 ArrayList 存儲(chǔ)。桶的數(shù)量為(maxmin)/arr.length+1

3、遍歷數(shù)組 arr，計(jì)算每個(gè)元素 arr[i] 放的桶

4、每個(gè)桶各自排序

代碼示例：

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]);
    }
    //創(chuàng)建桶
    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>());
    }
    //將每個(gè)元素放入桶
    for(int i = 0; i < arr.length; i++){
        int num = (arr[i] - min) / (arr.length);
        bucketArr.get(num).add(arr[i]);
    }
    //對(duì)每個(gè)桶進(jìn)行排序
    for(int i = 0; i < bucketArr.size(); i++){
        Collections.sort(bucketArr.get(i));
    }
}

基數(shù)排序算法

簡(jiǎn)介

基本思想：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后,數(shù)列就變成一個(gè)有序序列。

使用

應(yīng)用場(chǎng)景：用于大量數(shù)，很長(zhǎng)的數(shù)進(jìn)行排序時(shí)的情況。

步驟：

1、將所有的數(shù)的個(gè)位數(shù)取出，按照個(gè)位數(shù)進(jìn)行排序，構(gòu)成一個(gè)序列。

2、將新構(gòu)成的所有的數(shù)的十位數(shù)取出，按照十位數(shù)進(jìn)行排序，構(gòu)成一個(gè)序列。

代碼示例：

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,25,53,51};

  public radixSort(){
        sort(a);
        for(inti=0;i<a.length;i++){
            System.out.println(a[i]);
        }
  }

    public void sort(int[] array){
        //首先確定排序的趟數(shù);
        int max=array[0];
        for(inti=1;i<array.length;i++){
            if(array[i]>max){
                max=array[i];
            }
    }
        int time=0;
        //判斷位數(shù);
        while(max>0){
            max/=10;
            time++;
        }
        //建立 10 個(gè)隊(duì)列;
        List<ArrayList> queue=newArrayList<ArrayList>();
        for(int i=0;i<10;i++){
            ArrayList<Integer>queue1=new ArrayList<Integer>();
            queue.add(queue1);
        }
        //進(jìn)行 time 次分配和收集;
        for(int i=0;i<time;i++){
            //分配數(shù)組元素;
           for(intj=0;j<array.length;j++){
                //得到數(shù)字的第 time+1 位數(shù);
                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;//元素計(jì)數(shù)器;
            //收集隊(duì)列元素;
            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++;
                }
      }
    }
  }
}

剪枝算法

簡(jiǎn)介

基本思想：在搜索算法中優(yōu)化中，剪枝，就是通過某種判斷，避免一些不必要的遍歷過程，形象的說，就是剪去了搜索樹中的某些“枝條”，故稱剪枝。應(yīng)用剪枝優(yōu)化的核心問題是設(shè)計(jì)剪枝判斷方法，即確定哪些枝條應(yīng)當(dāng)舍棄，哪些枝條應(yīng)當(dāng)保留的方法。

使用

應(yīng)用場(chǎng)景：通常應(yīng)用在 DFS 和 BFS 搜索算法中，尋找過濾條件，提前減少不必要的搜索路徑。

步驟：

1、基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大；

2、用驗(yàn)證數(shù)據(jù)集最已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，這時(shí)用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)

代碼示例：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        LinkedList<Integer> track = new LinkedList<>();
        combinationSum(candidates, 0, target, track);
        return result;
    }

    private List<List<Integer>> result = new ArrayList<>();

    private void combinationSum(int[] candidates, int start, int target, LinkedList<Integer> track) {
        if (target < 0) {
            return;
        } else if (target == 0) {
            result.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (target < candidates[i]) {
                break;
            }
            track.add(candidates[i]);
            combinationSum(candidates, i, target - candidates[i], track);
            track.removeLast();
        }

    }
}

回溯算法

簡(jiǎn)介

基本思想：回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯”返回，嘗試別的路徑。

使用

應(yīng)用場(chǎng)景：設(shè)置一個(gè)遞歸函數(shù)，函數(shù)的參數(shù)會(huì)攜帶一些當(dāng)前的可能解的信息，根據(jù)這些參數(shù)得出可能解或者不可能而回溯，平時(shí)經(jīng)常見的有 N 皇后、數(shù)獨(dú)、集合等情況。

步驟：

1、定義一個(gè)解空間，它包含問題的解；

2、利用適于搜索的方法組織解空間；

3、利用深度優(yōu)先法搜索解空間；

4、利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。

代碼示例：

function backtrack(n, used) {
    // 判斷輸入或者狀態(tài)是否非法
    if (input/state is invalid) {
        return;
      }
    // 判讀遞歸是否應(yīng)當(dāng)結(jié)束，滿足結(jié)束條件就返回結(jié)果
    if (match condition) {
        return some value;
      }
    // 遍歷當(dāng)前所有可能出現(xiàn)的情況，并嘗試每一種情況
    for (all possible cases) {
        // 如果上一步嘗試會(huì)影響下一步嘗試，需要寫入狀態(tài)
        used.push(case)
        // 遞歸進(jìn)行下一步嘗試，搜索該子樹
        result = backtrack(n + 1, used)
        // 在這種情況下已經(jīng)嘗試完畢，重置狀態(tài)，以便于下面的回溯嘗試
        used.pop(case)
    } 
}

最短路徑算法

簡(jiǎn)介

基本思想：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑叫做最短路徑。解決最短路的問題有以下算法，Dijkstra 算法，Bellman-Ford 算法，F(xiàn)loyd 算法和 SPFA 算法等。

使用

應(yīng)用場(chǎng)景：應(yīng)用有計(jì)算機(jī)網(wǎng)絡(luò)路由算法，機(jī)器人探路，交通路線導(dǎo)航，人工智能，游戲設(shè)計(jì)等。

步驟：（Dijkstra 算法示例）

1、 訪問路網(wǎng)中里起始點(diǎn)最近且沒有被檢查過的點(diǎn)，把這個(gè)點(diǎn)放入 OPEN 組中等待檢查。

2、 從OPEN表中找出距起始點(diǎn)最近的點(diǎn)，找出這個(gè)點(diǎn)的所有子節(jié)點(diǎn)，把這個(gè)點(diǎn)放到 CLOSE 表中。

3、 遍歷考察這個(gè)點(diǎn)的子節(jié)點(diǎn)。求出這些子節(jié)點(diǎn)距起始點(diǎn)的距離值，放子節(jié)點(diǎn)到 OPEN 表中。

4、重復(fù)2，3，步。直到 OPEN 表為空，或找到目標(biāo)點(diǎn)。

代碼示例：

//Dijkstra 算法
static int[] pathSrc = new int[9];
static int[] shortPath = new int[9];
static void shortestPath_DijkStra(MGraph m, int v0) {    
    // finalPath[w] = 1 表示已經(jīng)獲取到頂點(diǎn)V0到Vw的最短路徑    
    int[] finalPath = new int[9];    
    for (int i = 0; i < m.numVertexes; i++) {        
        finalPath[i] = 0;        
        shortPath[i] = m.arc[v0][i];        
        pathSrc[i] = 0;    
    }    
    // v0到v0的路徑為0    
    shortPath[v0] = 0;    
    // vo到v0不需要求路徑    
    finalPath[v0] = 1;    
    for (int i = 1; i < m.numVertexes; i++) {        
        // 當(dāng)前所知的離V0最近的距離        
        int min = INFINITY;        
        int k = 0;        
        for (int w = 0; w < m.numVertexes; w++) {            
            if(shortPath[w] < min && finalPath[w] == 0) {                
                min = shortPath [w];                
                k = w;            
            }        
        }  
        finalPath[k] = 1; // 修改finalPath的值，標(biāo)記為已經(jīng)找到最短路徑
        for (int w = 0; w < m.numVertexes; w++) {            
            // 如果經(jīng)過V頂點(diǎn)的路徑比原來的路徑（不經(jīng)過V）短的話            
            if(finalPath[w] == 0 && (min + m.arc[k][w]) < shortPath[w]) {       
                // 說明找到了更短的路徑，修改                
                shortPath[w] = min + m.arc[k][w]; // 修改路徑的長(zhǎng)度
                pathSrc[w] = k; // 修改頂點(diǎn)下標(biāo)W的前驅(qū)頂點(diǎn)
            }        
        }    
    }
}

最大子數(shù)組算法

簡(jiǎn)介

基本思想：給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

使用

應(yīng)用場(chǎng)景：生活中可以用來查看股票一周之內(nèi)的增長(zhǎng)狀態(tài)，需要得到最合適的買入和賣出時(shí)間。

步驟：

1、將子串和為負(fù)數(shù)的子串丟掉，只留和為正的子串。

2、如果 nums 中有正數(shù)，從左到右遍歷 nums，用變量 cur 記錄每一步的累加和，遍歷到正數(shù) cur 增加，遍歷到負(fù)數(shù) cur 減少。

3、當(dāng) cur>=0 時(shí)，每一次累加都可能是最大的累加和，所以，用另外一個(gè)變量 max 全程跟蹤記錄 cur 出現(xiàn)的最大值即可。

代碼示例：

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    int maxSubArray(vector<int> nums) {
        if(nums.size()<=0){
            return 0;
        } 
        int max=INT_MIN,cur=0;//c++最小值
        for(int i=0; i<nums.size(); i++)  
        {  
            if(cur < 0)
                cur = nums[i];//如果前面加起來的和小于0，拋棄前面的
            else
                cur+=nums[i];

            if(cur > max)
                max = cur;
        }  
        return max;  

    }
};

最長(zhǎng)公共子序算法

簡(jiǎn)介

基本思想：最長(zhǎng)公共子序列是一個(gè)在一個(gè)序列集合中用來查找所有序列中最長(zhǎng)子序列的問題。這與查找最長(zhǎng)公共子串的問題不同的地方是：子序列不需要在原序列中占用連續(xù)的位置。

使用

應(yīng)用場(chǎng)景：最長(zhǎng)公共子序列問題是一個(gè)經(jīng)典的計(jì)算機(jī)科學(xué)問題，也是數(shù)據(jù)比較程序，比如 Diff 工具，和生物信息學(xué)應(yīng)用的基礎(chǔ)。它也被廣泛地應(yīng)用在版本控制，比如 Git 用來調(diào)和文件之間的改變。

步驟：

1、可以使用遞歸去解決，需要遍歷出所有的可能，很慢；

2、對(duì)于一般的 LCS 問題，都屬于 NP 問題；

3、當(dāng)數(shù)列的量為一定的時(shí)，都可以采用動(dòng)態(tài)規(guī)劃去解決。

代碼示例：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length();
        int length2 = text2.length();
        int[][] a = new int[length1 + 1][length2 + 1];//0行0列保留
        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    a[i][j] = a[i - 1][j - 1] + 1;
                } else {
                    if (a[i][j - 1] > a[i-1][j]) {
                        a[i][j] = a[i][j - 1];
                    } else {
                        a[i][j] = a[i - 1][j];
                    }
                }
            }
        }
        return a[length1][length2];
    }
}

最小生成樹算法

簡(jiǎn)介

基本思想：在含有n個(gè)頂點(diǎn)的帶權(quán)無向連通圖中選擇n-1條邊，構(gòu)成一棵極小連通子圖，并使該連通子圖中n-1條邊上權(quán)值之和達(dá)到最小，則稱其為連通網(wǎng)的最小生成樹（不一定唯一）。

一般情況，要解決最小生成樹問題，通常采用兩種算法：Prim算法和Kruskal算法。

使用

應(yīng)用場(chǎng)景：一般用來計(jì)算成本最小化的情況。

步驟：（Prim 算法示例）

1、以某一個(gè)點(diǎn)開始，尋找當(dāng)前該點(diǎn)可以訪問的所有的邊；

2、在已經(jīng)尋找的邊中發(fā)現(xiàn)最小邊，這個(gè)邊必須有一個(gè)點(diǎn)還沒有訪問過，將還沒有訪問的點(diǎn)加入我們的集合，記錄添加的邊；

3、尋找當(dāng)前集合可以訪問的所有邊，重復(fù) 2 的過程，直到?jīng)]有新的點(diǎn)可以加入；

4、此時(shí)由所有邊構(gòu)成的樹即為最小生成樹。

/** prim算法
    * @param first  構(gòu)成最小生成樹的起點(diǎn)的標(biāo)識(shí)
    * @return  返回最小生成樹構(gòu)成的邊
    */
public List<Edge> generateMinTreePrim(T first){
    //存儲(chǔ)最小生成樹構(gòu)成的邊
    List<Edge> result=new LinkedList<>();
    //首先建立map，key為vertex，value為edge
    HashMap<Vertex<T>, Edge> map=new HashMap<>();
    Iterator<Vertex<T>> vertexIterator=getVertexIterator();
    Vertex<T> vertex;
    Edge edge;
    while(vertexIterator.hasNext()){
        //一開始，value為edge的兩端的都為自己，weight=maxDouble
        vertex=vertexIterator.next();
        edge=new Edge(vertex, vertex, Double.MAX_VALUE);
        map.put(vertex, edge);
    }
    //first是構(gòu)成最小生成樹的起點(diǎn)的標(biāo)識(shí)
    vertex=vertexMap.get(first);
    if(vertex==null){
        System.out.println("沒有節(jié)點(diǎn)："+first);
        return result;
    }
    //所有不在生成樹中的節(jié)點(diǎn)，都是map的key,如果map為空，代表所有節(jié)點(diǎn)都在樹中
    while(!map.isEmpty()){
        //這次循環(huán)要加入生成樹的節(jié)點(diǎn)為vertex，邊為vertex對(duì)應(yīng)的edge（也就是最小的邊）
        edge=map.get(vertex);
        //每將一個(gè)結(jié)點(diǎn)j加入了樹A，首先從map中去除這個(gè)節(jié)點(diǎn)
        map.remove(vertex);
        result.add(edge);
        System.out.println("生成樹加入邊，頂點(diǎn)："+vertex.getLabel()+
                " ，邊的終點(diǎn)是："+edge.getEndVertex().getLabel()+" ，邊的權(quán)值為： "+edge.getWeight());;
        //如果是第一個(gè)節(jié)點(diǎn)，對(duì)應(yīng)的邊是到自己的，刪除
        if(vertex.getLabel().equals(first)){
            result.remove(edge);
        }
        //然后看map中剩余的節(jié)點(diǎn)到節(jié)點(diǎn)j的距離，如果這個(gè)邊的距離小于之前邊的距離，就將邊替換成這個(gè)到節(jié)點(diǎn)j的邊
        //在遍歷替換中，同時(shí)發(fā)現(xiàn)距離最短的邊minEdge
        Edge minEdge=new Edge(vertex, vertex, Double.MAX_VALUE);
        for(Vertex<T> now:map.keySet()){
            edge=map.get(now);
            //newEdge為now到節(jié)點(diǎn)j的邊
            Edge newEdge=now.hasNeighbourVertex(vertex);
            if(newEdge!=null&&newEdge.getWeight()<edge.getWeight()){
                //如果這個(gè)邊的距離小于之前邊的距離，就將邊替換成這個(gè)到節(jié)點(diǎn)j的邊
                edge=newEdge;
                map.put(now, edge);
            }
            if(edge.getWeight()<minEdge.getWeight()){
                //更新minEdge
                minEdge=edge;
            }
        }
        //這里設(shè)定邊的方向是不在樹上的v（為起始點(diǎn)）到樹上的u
        //這條邊的起始點(diǎn)是不在樹上的，是下一個(gè)加入生成樹的節(jié)點(diǎn)
        vertex=minEdge.getBeginVertex();            
    }       
    return result;
}

最后

算法無論是對(duì)于學(xué)習(xí)還是工作，都是必不可少的。如果說我們掌握了這些算法背后的邏輯思想，那么是會(huì)對(duì)我們的學(xué)習(xí)和工作有很好的促進(jìn)作用的。

其次算法對(duì)于面試，尤其是進(jìn)入一些大廠 BAT 等公司都是一塊敲門磚，大公司都會(huì)通過算法來評(píng)估你的整體技術(shù)水平，如果你有很好的算法功底，相信對(duì)你未來的職場(chǎng)道路也會(huì)有很大幫助。

在職業(yè)發(fā)展后期，擁有良好的算法技能，可以幫助我們更快、更高效的完成編碼，往架構(gòu)師的方向發(fā)展，同樣的崗位，你有相應(yīng)的算法知識(shí)的話，能拿到的薪資也會(huì)比別人更好一點(diǎn)。

當(dāng)然，算法遠(yuǎn)不止這些羅列的，還有很多復(fù)雜的算法需要去不斷學(xué)習(xí)，一起加油吧～