0. 算法是什么

算法是針對具體的問題設(shè)計解決問題的具體流程畅厢，并且有評價該處理流程的可量化的指標(biāo)饭寺。

1. 算法分類

算法也有很多的分類傅事，簡單來說的話，可以分為明確具體的流程宪郊，和明確嘗試的具體的流程兩類掂恕。

• 明確具體的流程（a+b）
• 明確嘗試的具體流程（a的所有的素數(shù)）

2. 入門級別的算法題目

題目一：1!+2!+3!+...+n! 的結(jié)果

• 算法思路：
  1! = 1
  2! = 1 2
  3! = 1 2 3
  ......
  n! = 1 2 3 ... n
  所以拖陆，1!+2!+3!+...+n! = 1 + 1 2 + 1 2 3 + ... + 1 2 3 ... n
  此時，我們假設(shè)每一個數(shù)字是 i, 一共有n個數(shù)懊亡，我們分別求得i的階乘依啰，然后想加起來。循環(huán)n遍即可得店枣。
  代碼如下：

  public static void factorial1(int n){
        int sum = 0;
//從1～n個數(shù)
        for(int i = 1; i <= n; i++){
            int curSum = 1;
//對每個i的數(shù)字求其階乘速警，1 * 2  * ...i 
            for(int j = 1; j <= i; j++){
                curSum *= j;
            }
            sum += curSum;
        }
        System.out.println(sum);
    }

這個算法思路解決了我們的問題，那我們看一下這個代碼鸯两，有兩個for循環(huán)闷旧，復(fù)雜度偏高，有沒有再優(yōu)化一下的思路呢钧唐。我們觀察忙灼，后一個的階乘是建立在前一個階乘的結(jié)果之上的。

• 優(yōu)化思路：
  2! = 1! 2
  3! = 2! 3
  ...
  n! = (n-1)! n
  那么我們就不必重復(fù)去求得前一個數(shù)的階乘了钝侠，保存下來即可缀棍。
  優(yōu)化代碼：

public static void factorial(int n){
        int sum = 0;
        int facNum = 1;
        for (int i = 1; i <= n; i++){
            facNum *= i;
            sum += facNum;
        }
        System.out.println(sum);
    }

這個代碼可以清楚地看到我們少了一個for循環(huán)，復(fù)雜度大大下降机错。
至此，求階乘的問題已經(jīng)解決了父腕，很多時候弱匪，我們拿到問題時，都不能一下子想到那個最優(yōu)解璧亮，沒關(guān)系萧诫，我們可以慢慢來，一步步分析枝嘶，先做到有那個最不優(yōu)的算法帘饶，然后再觀察，看是否可以進(jìn)一步優(yōu)化即可群扶。

題目二：選擇排序

算法思路：
在0～n-1位置找最小值及刻，交換放在0號位置；
在1～n-1位置找最小值竞阐，交換放在1號位置缴饭；
...
在n-2～n-1位置找最小值，交換放在n-2位置骆莹；
每輪都選出最小值颗搂，然后放在相應(yīng)的位置。

image.png

image.png

最終幕垦，這個數(shù)組就會被每輪選擇最小值然后交換丢氢，成為從小到大的有序數(shù)組傅联。

代碼如下：

   public static void selectSort(int[] arr){

        if(null == arr || arr.length < 2){
            return;
        }

        for(int i = 0; i < arr.length -1 ; i++){
            int minValueIndex = i;
            for(int j = i + 1; j < arr.length; j++){
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            swap(arr, i, minValueIndex);
        }
    }

題目三：冒泡排序

算法思路：兩兩比較，較大的數(shù)向右移疚察。
在0~n-1 邊比較邊右移蒸走，將大的數(shù)向右沉；（最大的數(shù)在n-1位置）
在0～n-2 邊比較邊右移... （第二大的數(shù)在n-2位置）
...

image.png

image.png

一輪輪的比較交換比較交換后稍浆，數(shù)組就會成為從小到大的有序數(shù)組载碌。
代碼如下：

  public static void bubbleSort(int[] arr){
        if(null == arr || arr.length <2){
            return;
        }

        for(int end = arr.length-1; end >= 0; end --){
            for(int start = 0; start < end; start ++){
                if(arr[start] > arr[start+1]){
                    swap(arr, start, start+1);
                }
            }
        }
    }

題目四：插入排序

算法思路：局部形成有序，來一個數(shù)衅枫，進(jìn)行從右向左的比較嫁艇，將它插入在合適的位置。
在0位置有序弦撩；
在0～1位置有序步咪；
在0～2位置有序；
...

image.png

代碼如下：

public static void insertSort(int[] arr){
        if(null == arr || arr.length < 2){
            return;
        }

        for(int i = 1; i < arr.length; i++){
            for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--){
                swap(arr, j, j+1);
            }
        }
    }

3. 總結(jié)

算法就是解決問題的處理流程益楼。
我們可以看到選擇排序猾漫，冒泡排序，插入排序都是復(fù)雜度為o(),且頻繁交換或者頻繁比較感凤，說明這三個排序并不算是性能最好的排序悯周，但是它們易于理解和代碼編寫，算是新手入門的最佳例題陪竿。