前言

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

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

算法簡介

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

image-20210324175721795

1. 算法五大特性

• 有窮性：一個(gè)算法必須在執(zhí)行有限步之后結(jié)束，且每一步都可在有限時(shí)間內(nèi)完成。通俗一點(diǎn)理解就是不能出現(xiàn)類似死循環(huán)這樣，導(dǎo)致算法無法結(jié)束。
• 確定性：算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出。
• 可行性：算法中描述的每一步操作都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。
• 輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。就好比一個(gè)方法，可以不傳遞參數(shù)，也可以傳遞參數(shù)。零個(gè)輸入時(shí)其實(shí)代表算法本身設(shè)有初始條件。
• 輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是與輸入有著對應(yīng)關(guān)系的量。沒有輸出的算法是毫無意義的。

一個(gè)好的算法還應(yīng)該有如下特征：

• 正確性：能正確解決問題，結(jié)果正確；
• 可讀性：算法實(shí)現(xiàn)步驟容易讀懂；
• 健壯性：算法能處理異常情況；比如輸入不合法時(shí)，算法能給出對應(yīng)處理；
• 高效率、低存儲(chǔ)：時(shí)間復(fù)雜度低，空間復(fù)雜度低；即運(yùn)行快，占用內(nèi)存少。

2. 衡量算法好壞的標(biāo)準(zhǔn)

度量一個(gè)算法好壞，可以從兩個(gè)維度進(jìn)行判斷：

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

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

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

  image-20210325084348799

  上圖方法，為了方便理解，假設(shè)每一步需要1ms，當(dāng)傳入的n=1000時(shí)，每一步耗時(shí)如下：

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

  ②由于每次循環(huán)需要判斷，需要?jiǎng)t需要1001次；消耗1001ms；

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

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

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

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

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

  因?yàn)楫?dāng)n足夠大時(shí)，系數(shù)和常數(shù)對算法度量的影響不大；這里就不細(xì)說啦；

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

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

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

O(1)<O(log₂ n)<O(n)<O(nlog₂ n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

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

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

從排序開始

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

• 內(nèi)部排序：在排序期間元素全部存在內(nèi)存中進(jìn)行排序；常見的插入排序、交換排序、選擇排序都是內(nèi)部排序。
• 外部排序：在排序期間元素?zé)o法全部存放在內(nèi)存中，必須在排序過程中不斷地在內(nèi)、外存之間移動(dòng)。

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

1.1 算法思想

插入排序就是每次將一個(gè)待排序的數(shù)據(jù)插入到一個(gè)前面已排好序的子序列中，初始認(rèn)為第一個(gè)元素就是排好序的序列，依次比較，然后插入到合適位置，直到完成排序?yàn)橹埂?/p>

插入排序的關(guān)鍵如下：

• 將待排序數(shù)據(jù)分為三部分，已經(jīng)排好序的數(shù)據(jù)、下一個(gè)需要插入的數(shù)據(jù)、待排序的數(shù)據(jù)；
• 每一次都從待排序數(shù)據(jù)中取出一個(gè)需要插入的數(shù)據(jù)，將其放在哨兵位置；
• 將哨兵位置的數(shù)據(jù)(其實(shí)就是要插入的數(shù)據(jù))與已排好序的數(shù)據(jù)進(jìn)行比較，如果符合條件就插入到對應(yīng)位置，其他數(shù)據(jù)統(tǒng)一向后移位即可；

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

算法代碼如下(升序)：

image-20210325135045509

執(zhí)行結(jié)果如下：

image-20210325134622616

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

image-20210325214501972

步驟說明：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

image-20210325235648402

1.3 算法分析

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

時(shí)間復(fù)雜度

分析時(shí)間復(fù)雜度時(shí)，會(huì)從最好、平均、最壞三種情況進(jìn)行分析；

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

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

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

空間復(fù)雜度

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

穩(wěn)定性

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

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

總結(jié)

第一篇復(fù)習(xí)了一下關(guān)于算法相關(guān)知識(shí)，然后以簡單的直接插入排序收尾，后面會(huì)依次總結(jié)其他算法，還是圖解加說明的方式，讓每一個(gè)算法學(xué)起來更簡單。

感謝小伙伴的：點(diǎn)贊、收藏和評論，下期繼續(xù)~~~

一個(gè)被程序搞丑的帥小伙，關(guān)注"Code綜藝圈"，跟我一起學(xué)~~~