前言

程序=數(shù)據(jù)結構+算法，好的算法能讓程序更高效的運行；在當今數(shù)據(jù)信息時代，數(shù)據(jù)分析和數(shù)據(jù)處理肯定是避免不了，而算法便成為了很多公司門檻級的要求，特別是大廠；

趕緊搞起來，說不定離進大廠就只差一步呢(算法)~~~

算法簡介

算法是一組完成任務的指令，任何代碼片段都可視為算法。如下：

image-20210324175721795

1. 算法五大特性

• 有窮性：一個算法必須在執(zhí)行有限步之后結束，且每一步都可在有限時間內完成。通俗一點理解就是不能出現(xiàn)類似死循環(huán)這樣，導致算法無法結束。

• 確定性：算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出。

• 可行性：算法中描述的每一步操作都可以通過已經實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。

• 輸入：一個算法有零個或多個輸入。就好比一個方法，可以不傳遞參數(shù)，也可以傳遞參數(shù)。零個輸入時其實代表算法本身設有初始條件。

• 輸出：一個算法有一個或多個輸出，這些輸出是與輸入有著對應關系的量。沒有輸出的算法是毫無意義的。

一個好的算法還應該有如下特征：

• 正確性：能正確解決問題，結果正確；

• 可讀性：算法實現(xiàn)步驟容易讀懂；

• 健壯性：算法能處理異常情況；比如輸入不合法時，算法能給出對應處理；

• 高效率、低存儲：時間復雜度低，空間復雜度低；即運行快，占用內存少。

2. 衡量算法好壞的標準

度量一個算法好壞，可以從兩個維度進行判斷：

• 時間復雜度：事先預估執(zhí)行完算法的時間開銷數(shù)量級；

  由于數(shù)據(jù)量多少、硬件配置、程序語言等因素會直接影響到算法的執(zhí)行時間，比如同樣的算法，數(shù)據(jù)量少的肯定快，硬件配置高的肯定快，所以不能用算法執(zhí)行完成后的具體時間來衡量一個算法的好壞。

  一個算法，可以預估其時間開銷級別(不受外界其他條件影響)，通常使用大O表示法來表示，來個例子：

  image-20210325084348799

  上圖方法，為了方便理解，假設每一步需要1ms，當傳入的n=1000時，每一步耗時如下：

  ①只執(zhí)行一次，所以消耗1ms；

  ②由于每次循環(huán)需要判斷，需要則需要1001次；消耗1001ms；

  ③和④在循環(huán)體中，所以分別需要執(zhí)行1000次，總共消耗2000ms；

  所以總耗時為：T(1000)=1+1001+2*1000；具體時間和傳入的n有關系，則總耗時為：

  T(n)=1+(n+1)+2n；

  這里T代表時間，通常說時間復雜度的時候都不帶單位。為了更加簡潔直觀，會使用大O表示法，去掉常數(shù)部分和系數(shù)部分，如下：

  T(n)=1+(n+1)+2n=O(n)；

  因為當n足夠大時，系數(shù)和常數(shù)對算法度量的影響不大；這里就不細說啦；

• 空間復雜度：事先預估執(zhí)行完算法的內存開銷數(shù)量級 ；

  空間復雜度和時間復雜度類似，同樣可以用大O表示，只是這個表示的是算法所消耗的內存，比如int占用4個字節(jié)，上圖中用到中間變量nResult，在不考慮其他容量的情況下，消耗了4個字節(jié)，用大O表示法，依然是去掉常數(shù)和系數(shù)，對于常量的的表示為O(1)；

對于時間復雜度和空間復雜度，對應的數(shù)量級別越小，算法越高效。常遇到到級別從好到差的順序如下：

3. 算法的穩(wěn)定性

若待排序數(shù)據(jù)中有兩個相等的元素A和B，在排序前A在B前面，如果使用某種排序算法后，A仍在B前面，則稱這種排序算法穩(wěn)定，否則就不穩(wěn)定。但穩(wěn)定性不能用來衡量一個算法的好壞，只能算是算法的一個性質，對于一些場景，根本就不在乎兩個相等元素的順序。

從排序開始

排序在實際開發(fā)中用的比較多，就先從這入手吧；排序分為內部排序和外部排序兩種：

• 內部排序：在排序期間元素全部存在內存中進行排序；常見的插入排序、交換排序、選擇排序都是內部排序。

• 外部排序：在排序期間元素無法全部存放在內存中，必須在排序過程中不斷地在內、外存之間移動。

1. 先來說說直接插入排序

1.1 算法思想

插入排序就是每次將一個待排序的數(shù)據(jù)插入到一個前面已排好序的子序列中，初始認為第一個元素就是排好序的序列，依次比較，然后插入到合適位置，直到完成排序為止。

插入排序的關鍵如下：

• 將待排序數(shù)據(jù)分為三部分，已經排好序的數(shù)據(jù)、下一個需要插入的數(shù)據(jù)、待排序的數(shù)據(jù)；

• 每一次都從待排序數(shù)據(jù)中取出一個需要插入的數(shù)據(jù)，將其放在哨兵位置；

• 將哨兵位置的數(shù)據(jù)(其實就是要插入的數(shù)據(jù))與已排好序的數(shù)據(jù)進行比較，如果符合條件就插入到對應位置，其他數(shù)據(jù)統(tǒng)一向后移位即可；

1.2 算法實現(xiàn)與解析

算法代碼如下(升序)：

image-20210325135045509

執(zhí)行結果如下：

image-20210325134622616

解析排序步驟過程，如下：

image-20210325214501972

步驟說明：

圖中綠線框部分代表是已經排好序的列表，箭頭指的元素是下一個要插入的元素，黃線框部分為剩下的無序元素。黃方塊為每次移動的數(shù)據(jù)，綠方塊表示最后有序列表騰出的位置。

• 將原始數(shù)據(jù)array復制到新數(shù)組中arrayb中，這步的主要目的是后續(xù)不需要聲明額外臨時變量，也為了后續(xù)核心代碼實現(xiàn)邏輯簡單易懂，減少過多的判斷；

• 第1步將第一個元素作為有序列表(第一元素為2)，下一個要插入的元素為5，將5放入哨兵位置，即索引為0的位置；然后依次遍歷有序列表中的元素，與哨兵位的值5比較，這里只有2和5比較，2小于5，所以不需要改變位置；

• 第2步有序列表中的元素有2和5,下一個要插入的元素為6，將6放入哨兵位置，即索引為0的位置；然后依次遍歷有序列表中的元素(2和5)，與哨兵位的值6比較，都小于6，所以不需要改變位置；

• 第3步有序列表中的元素有2、5、6,下一個要插入的元素為1，將1放入哨兵位置，即索引為0的位置；然后依次遍歷有序列表中的元素(2、5、6)，與哨兵位的值1比較；

  第3-1步，由于是倒序遍歷，先用有序列表中的6與1進行比較，6大于1，所以6往后移一位；

  第3-2步，繼續(xù)遍歷，用有序列表中的5與1進行比較，5大于1，所以5往后移一位；

  第3-3步，繼續(xù)遍歷，用有序列表中的2與1進行比較，2大于1，所以2往后移一位；

  第3-4步，遍歷完有序列表中的元素，要插入的元素和哨兵位的元素相等，終止遍歷；然后將哨兵位的元素(當前哨兵位為1)賦值給騰出的空間(騰出的索引位為1)；

• 第4步有序列表中的元素有1、2、5、6,下一個要插入的元素為9，將9放入哨兵位置，即索引為0的位置；然后依次遍歷有序列表中的元素(1、2、5、6)，都小于哨兵位的值9，所以不用插入，位置不變；

• 第5步有序列表中的元素有1、2、5、6、9,下一個要插入的元素為3，將3放入哨兵位置，即索引為0的位置；然后依次遍歷有序列表中的元素(1、2、5、6、9)，與哨兵位的值3比較；

  第5-1步，由于是倒序遍歷，先用有序列表中的9與3進行比較，9大于3，所以9往后移一位；

  第5-2步，繼續(xù)遍歷，用有序列表中的6與3進行比較，6大于3，所以6往后移一位；

  第5-3步，繼續(xù)遍歷，用有序列表中的5與3進行比較，5大于3，所以5往后移一位；

  第5-4步，繼續(xù)遍歷，用有序列表中的2與3進行比較，2小于3，終止遍歷；然后將哨兵位的元素(當前哨兵位為3)賦值給騰出的空間(騰出的索引位為3)；

第5步完成之后，已完成黃線框中無序元素的排序，排序也就完成啦；最終的結果就是1、2 、3 、5 、6 、9。

這樣對比著圖看詳細說明，是不是好理解了很多。

如果有小伙伴不太理解上面的代碼，可以使用定義臨時變量作為哨兵的方式，步驟和上面基本一樣，只是哨兵不一樣，如下：

image-20210325235648402

1.3 算法分析

主要從時間復雜度、空間復雜度、是否穩(wěn)定來進行分析：

時間復雜度

分析時間復雜度時，會從最好、平均、最壞三種情況進行分析；

最好時間復雜度：傳入的數(shù)據(jù)是有序的(和最終的結果一致)，所以每次遍歷，一次就能找到位置，所以插入排序的最好時間復雜度為O(n)，和傳入的元素個數(shù)有關；

最壞時間復雜度：傳入的數(shù)據(jù)完全和要的結果相反，所以每次都需要進行兩次循環(huán)進行找到合適位置插入，所以最壞時間復雜度為O(n²)；

平均時間復雜度也就是：O(n²)；

空間復雜度

在算法核心部分只采用了固定的幾個中間變量(i,j,arrayb[0])，所以算法過程中消耗的內存是一個常量，則空間復雜度為O(1)；

穩(wěn)定性

由于在算法過程中采用的是小于符號進行比較，遇見相等的數(shù)據(jù)時就終止判斷，所以不會影響原有的數(shù)據(jù)順序，則直接插入排序是穩(wěn)定的。

綜上所述，插入排序的時間復雜度為O(n²)，空間復雜度為O(1)，是穩(wěn)定算法；

總結

第一篇復習了一下關于算法相關知識，然后以簡單的直接插入排序收尾，后面會依次總結其他算法，還是圖解加說明的方式，讓每一個算法學起來更簡單。

總結

以上是生活随笔為你收集整理的大牛领导单独找我聊了两句：搞框架的同时别忘了算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。