前言

非常欣慰的看到如今越來越多的運維人員也開始學(xué)開發(fā)了，it's a good sign, 畢竟行業(yè)大勢不可違，我依然堅信，不出3年，不會開發(fā)的運維連工作都找不到，很多人可能依然嗤之以鼻，就像3年前我呼吁做運維的一定要會開發(fā)，最好是Python,一大堆腦子進水的小白還跑來跟我爭論不會開發(fā)也無所謂，說什么開發(fā)運維涇渭分明，還說什么做運維shell能玩熟就可以了，現(xiàn)在事實已經(jīng)狠狠的打了這些人的臉，只想說，各個行業(yè)里都有一大群后知后覺、腦子長在屁股上的人，目光短淺，根本看不清行業(yè)的大趨勢，呵呵，沒關(guān)系 ，因為最終這些人終將被淘汰。 

anyway,這不是今天的話題的重點，重點是很多人覺得會寫個腳本、寫個腳本就算會開發(fā)了，然并卵，如果只會寫一些不復(fù)雜的小程序，我不認(rèn)為這是會開發(fā)，或充其量只能叫入門級程序搬磚工， 如果想成為一名還不錯的程序員，掌握一些算法知識是必備技能，好多人覺得算法難學(xué)，沒錯，要想搞好算法它確實必寫普通程序要花的時間 多一些，但請相信我，常用算法并不算難，只是邏輯比較繞而已，多花點時間 ，一般人都能搞定 ，且當(dāng)你學(xué)會一些算法后就會發(fā)現(xiàn)，原來算法真的好有趣，換一個思路，就可以導(dǎo)致程序的執(zhí)行效率差距幾十甚至幾百倍。So,親們，接下來讓我?guī)Т蠹乙黄鹣葋韨€算法入門吧，如果大家喜歡，記得給好評后噢，后面會持續(xù)奉上更多算法相關(guān)專題，oh, let's do it. 

看完不明白的加群討論 （Python開發(fā)就業(yè)之路304154367）

另外，51cto學(xué)院正在搞最喜歡講師投票，看過我視頻并且覺得還不錯的親們歡迎投我一票 http://edu.51cto.com/activityvote/voteRanking/page-1.html  沒錯，長的最帥的那個就是我。  

什么是算法

1、什么是算法

算法(algorithm):就是定義良好的計算過程，他取一個或一組的值為輸入，并產(chǎn)生出一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)化成輸出結(jié)果。

2、算法的意義

假設(shè)計算機無限快，并且計算機存儲容器是免費的，我們還需要各種亂七八糟的算法嗎？如果計算機無限快，那么對于某一個問題來說，任何一個都可以解決他的正確方法都可以的！

當(dāng)然，計算機可以做到很快，但是不能做到無限快，存儲也可以很便宜但是不能做到免費。

那么問題就來了效率：解決同一個問題的各種不同算法的效率常常相差非常大，這種效率上的差距的影響往往比硬件和軟件方面的差距還要大。

3、如何選擇算法

第一首先要保證算法的正確性

一個算法對其每一個輸入的實例，都能輸出正確的結(jié)果并停止，則稱它是正確的，我們說一個正確的算法解決了給定的計算問題。不正確的算法對于某些輸入來說，可能根本不會停止，或者停止時給出的不是預(yù)期的結(jié)果。然而，與人們對不正確算法的看法想反，如果這些算法的錯誤率可以得到控制的話，它們有時候也是有用的。但是一般而言，我們還是僅關(guān)注正確的算法！

第二分析算法的時間復(fù)雜度

算法的時間復(fù)雜度反映了程序執(zhí)行時間隨輸入規(guī)模增長而增長的量級，在很大程度上能很好反映出算法的好壞。

時間復(fù)雜度

1、什么是時間復(fù)雜度

一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。
一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù),用T(n)表示,若有某個輔助函數(shù)f(n),使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。

2、時間復(fù)雜度的計算方法

一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試因為該方法有兩個缺陷：

• 想要對設(shè)計的算法的運行性能進行測評，必須先依據(jù)算法編寫相應(yīng)的程序并實際運行。

• 所得時間的統(tǒng)計計算依賴于計算機的硬件、軟件等環(huán)境因素，有時候容易掩蓋算法的本身優(yōu)勢。

所以只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。

一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是模塊n的某一個函數(shù)f(n),因此，算法的時間復(fù)雜度記做：T(n)=O(f(n))。隨著模塊n的增大，算法執(zhí)行的時間的增長率和f(n)的增長率成正比，所以f(n)越小，算法的時間復(fù)雜度越低,算法的效率越高。 

 在計算時間復(fù)雜度的時候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)，再找出T(n)的同數(shù)量級(它的同數(shù)量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n!)，找出后，f(n)=該數(shù)量級，若T(n)/f(n)求極限可得到一常數(shù)c，則時間復(fù)雜度T(n)=O(f(n))。

3、常見的時間復(fù)雜度

常見的算法時間復(fù)雜度由小到大依次為：

Ο(1)＜Ο(log₂n)＜Ο(n)＜Ο(nlog₂n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2ⁿ)＜Ο(n!)

 求解算法的時間復(fù)雜度的具體步驟：

• 找出算法中的基本語句，算法中執(zhí)行最多的那條語句是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。

• 計算基本語句的執(zhí)行次數(shù)的量級，保證最高次冪正確即可查看他的增長率。

• 用大O幾號表示算法的時間性能

 如果算法中包含鑲套的循環(huán)，則基本語句通常是最內(nèi)層的循環(huán)體，如果算法中包并列的循環(huán)，則將并列的循環(huán)時間復(fù)雜度相加，例如：

第一個for循環(huán)的時間復(fù)雜度為Ο(n)，第二個for循環(huán)的時間復(fù)雜度為Ο(n2)，則整個算法的時間復(fù)雜度為Ο(n+n2)=Ο(n2)。

Ο(1)表示基本語句的執(zhí)行次數(shù)是一個常數(shù)，一般來說，只要算法中不存在循環(huán)語句，其時間復(fù)雜度就是Ο(1)。

其中Ο(log₂n)、Ο(n)、 Ο(nlog₂n)、Ο(n²)和Ο(n³)稱為多項式時間,而Ο(2ⁿ)和Ο(n!)稱為指數(shù)時間，計算機科學(xué)家普遍認(rèn)為前者（即多項式時間復(fù)雜度的算法）是有效算法，把這類問題稱為P（Polynomial,多項式）類問題，而把后者（即指數(shù)時間復(fù)雜度的算法）稱為NP（Non-Deterministic Polynomial, 非確定多項式）問題。在選擇算法的時候，優(yōu)先選擇前者！

OK對于沒有算法基礎(chǔ)的同學(xué)，看起算法來也很頭疼，但是這個是基礎(chǔ)和重點，不會算法的開發(fā)不是一個合格的開發(fā)并且包括語言記得基礎(chǔ)也是需要好好整理的！加油吧~~  咱們在一起看下時間復(fù)雜度的詳細說明吧

常見的時間復(fù)雜度示例

1、O(1)

#O(1)n = 100 
sum = (1+n) * n/2 #執(zhí)行一次sum_1 = (n/2) - 10 #執(zhí)行一次sum_2 = n*4 - 10 + 8 /2 #執(zhí)行一次

這個算法的運行次數(shù)函數(shù)是f(n)=3。根據(jù)我們推導(dǎo)大O階的方法，第一步就是把常數(shù)項3改為1。在保留最高階項時發(fā)現(xiàn)，它根本沒有最高階項，所以這個算法的時間復(fù)雜度為O(1)。

并且：如果算法的執(zhí)行時間不隨著問題規(guī)模n的增長而增加，及時算法中有上千條語句，其執(zhí)行的時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度記作O(1)

2、O(n²)

n = 100 

for i in range(n): #執(zhí)行了n次
    for q in range(n): #執(zhí)行了n2
        print(q) #執(zhí)行了n2

解：T(n)=2n²+n+1 =O(n²)

一般情況下，對進循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，忽略該語句中步長加1、終值判別、控制轉(zhuǎn)移等成分，當(dāng)有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。  

3、O(n)   

#O(n)n =100 
a = 0 #執(zhí)行一次b = 1#執(zhí)行一次for i in range(n): #執(zhí)行n次
    s = a +b #執(zhí)行n-1次
    b =a #執(zhí)行n-1次
    a =s #執(zhí)行n-1次

解：T(n)=2+n+3(n-1)=4n-1=O(n)

4、Ο(n³)

#O(n3)n = 100for i in range(n):#執(zhí)行了n次
    for q in range(n):#執(zhí)行了n^2
        for e in range(n):#執(zhí)行了n^3
            print(e)#執(zhí)行了n^3

簡單點來去最大值是：Ο(n³)

排序?qū)嵗?/h2>

排序算法是在更復(fù)雜的算法中的是一個構(gòu)建基礎(chǔ)，所以先看下常用的排序。

1、冒泡排序

需求：

請按照從小到大對列表，進行排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] 

思路：相鄰兩個值進行比較，將較大的值放在右側(cè)，依次比較！

原理圖：

原理分析：

列表中有5個元素兩兩進行比較，如果左邊的值比右邊的值大,就用中間值進行循環(huán)替換！
既然這樣，我們還可以用一個循環(huán)把上面的循環(huán)進行在次循環(huán)，用表達式構(gòu)造出內(nèi)部循環(huán)！

代碼實現(xiàn)：

#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'import random

maopao_list = [13, 22, 6, 99, 11]'''原理分析:
列表中有5個元素兩兩進行比較，如果左邊的值比右邊的值大,就用中間值進行循環(huán)替換！
既然這樣，我們還可以用一個循環(huán)把上面的循環(huán)進行在次循環(huán)，用表達式構(gòu)造出內(nèi)部循環(huán)！'''def handler(array):    for i in range(len(array)):        for j in range(len(array)-1-i):            '''
            這里為什么要減1,我們看下如果里面有5個元素我們需要循環(huán)幾次?最后一個值和誰對比呢?對吧!所以需要減1
            這里為什么減i?,這個i是循環(huán)的下標(biāo),如果我們循環(huán)了一次之后最后一只值已經(jīng)是最大的了還有必要再進行一次對比嗎?沒有必要~            '''
            print('left:%d' % array[j],'right:%d' % array[j+1])            if array[j] > array[j+1]:
                tmp = array[j]
                array[j] = array[j+1]
                array[j+1] = tmpif __name__ == '__main__':
    handler(maopao_list)    print(maopao_list)

時間復(fù)雜度說明看下他的代碼復(fù)雜度會隨著N的增大而成指數(shù)型增長，并且根據(jù)判斷他時間復(fù)雜度為Ο(n²)

2、選擇排序

需求：

請按照從小到大對列表，進行排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] 

思路：

第一次，從列表最左邊開始元素為array[0]，往右循環(huán)，從右邊元素中找到小于array[0]的元素進行交換，直到右邊循環(huán)完之后。

第二次，左邊第一個元素現(xiàn)在是最小的了，就從array[1],和剩下的array[1:-1]內(nèi)進行對比，依次進行對比！

對比：

他和冒泡排序的區(qū)別就是，冒泡排序是相鄰的兩兩做對比，但是選擇排序是左側(cè)的“對比元素”和右側(cè)的列表內(nèi)值做對比！

原理圖：

代碼實現(xiàn)：

#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'xuanze_list = [13, 22, 6, 99, 11]print(range(len(xuanze_list)))def handler(array):    for i in range(len(array)):        '''
        循環(huán)整個列表        '''
        for j in range(i,len(array)):            '''
            這里的小循環(huán)里,循環(huán)也是整個列表但是他的起始值是i,當(dāng)這一個小循環(huán)完了之后最前面的肯定是已經(jīng)排序好的
            第二次的時候這個值是循環(huán)的第幾次的值比如第二次是1,那么循環(huán)的起始值就是array[1]            '''
            if array[i] > array[j]:
                temp = array[i]
                array[i] = array[j]
                array[j] = temp        # print(array)if __name__ == '__main__':
    handler(xuanze_list)    print(xuanze_list)

選擇排序代碼優(yōu)化：

#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'import randomimport timedef handler(array):    for i in range(len(array)):
        smallest_index = i  #假設(shè)默認(rèn)第一個值最小
        for j in range(i,len(array)):            if array[smallest_index] > array[j]:
                smallest_index = j  #如果找到更小的,記錄更小元素的下標(biāo)
        '''
        小的循環(huán)結(jié)束后在交換,這樣整個小循環(huán)就之前的選擇排序來說,少了很多的替換過程,就只替換了一次!提升了速度        '''
        tmp = array[i]
        array[i] = array[smallest_index]
        array[smallest_index] = tmpif __name__ == '__main__':
    array = []
    old_time = time.time()    for i in range(50000):
        array.append(random.randrange(1000000))
    handler(array)    print(array)    print('Cost time is :',time.time() - old_time)

3、插入排序

需求：

請按照從小到大對列表，進行排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] 

思路：

一個列表默認(rèn)分為左側(cè)為排序好的，我們拿第一個元素舉例，他左邊的全是排序好的，他右側(cè)是沒有排序好的，如果右側(cè)的元素小于左側(cè)排序好的列表的元素就把他插入到合適的位置

原理圖：

 

代碼實現(xiàn)：

#!/usr/bin/env python#-*- coding:utf-8 -*-__author__ = 'luotianshuai'import randomimport time
chaoru_list = [69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619]def handler(array):    for i in range(1,len(array)):
        position = i #剛開始往左邊走的第一個位置
        current_val = array[i] #先把當(dāng)前值存下來
        while position > 0 and current_val < array[position -1]:            '''
            這里為什么用while循環(huán),咱們在判斷左邊的值得時候知道他有多少個值嗎?不知道,所以用while循環(huán)
            什么時候停下來呢?當(dāng)左邊沒有值得時候,或者當(dāng)他大于左邊的值得時候!            '''
            array[position] = array[position - 1] #如果whille條件成立把當(dāng)前的值替換為他上一個值
            '''
            比如一個列表:
            [3,2,4,1]
            現(xiàn)在循環(huán)到 1了,他前面的元素已經(jīng)循環(huán)完了
            [2,3,4] 1

            首先我們記錄下當(dāng)前這個position的值 = 1
            [2,3,4,4] 這樣,就出一個位置了
            在對比前面的3,1比3小
            [2,3,3,4] 在替換一下他們的值
             在對比2
            [2,2,3,4]
            最后while不執(zhí)行了在進行替換'array[position] = current_val  #把值替換'            '''
            position -= 1        #當(dāng)上面的條件都不成立的時候{左邊沒有值/左邊的值不比自己的值小}
        array[position] = current_val  #把值替換if __name__ == '__main__':
    handler(chaoru_list)    print(chaoru_list)'''
    array = []#[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619]
    old_time = time.time()
    for i in range(50000):
        array.append(random.randrange(1000000))
    handler(array)
    print(array)
    print('Cost time is :',time.time() - old_time)'''

4、快速排序

設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結(jié)束時產(chǎn)生變動.他的時間復(fù)雜度是：O(nlogn) ~Ο(n²)

排序示例：

假設(shè)用戶輸入了如下數(shù)組：

創(chuàng)建變量i=0（指向第一個數(shù)據(jù)）[i所在位置紅色小旗子], j=5(指向最后一個數(shù)據(jù))[j所在位置藍色小旗子], k=6(賦值為第一個數(shù)據(jù)的值)。

我們要把所有比k小的數(shù)移動到k的左面，所以我們可以開始尋找比6小的數(shù)，從j開始，從右往左找，不斷遞減變量j的值，我們找到第一個下標(biāo)3的數(shù)據(jù)比6小，于是把數(shù)據(jù)3移到下標(biāo)0的位置，把下標(biāo)0的數(shù)據(jù)6移到下標(biāo)3，完成第一次比較：

i=0 j=3 k=6

接著，開始第二次比較，這次要變成找比k大的了，而且要從前往后找了。遞加變量i，發(fā)現(xiàn)下標(biāo)2的數(shù)據(jù)是第一個比k大的，于是用下標(biāo)2的數(shù)據(jù)7和j指向的下標(biāo)3的數(shù)據(jù)的6做交換，數(shù)據(jù)狀態(tài)變成下表：

 i=2 j=3 k=6

稱上面兩次比較為一個循環(huán)。

接著，再遞減變量j，不斷重復(fù)進行上面的循環(huán)比較。

在本例中，我們進行一次循環(huán)，就發(fā)現(xiàn)i和j“碰頭”了：他們都指向了下標(biāo)2。于是，第一遍比較結(jié)束。得到結(jié)果如下，凡是k(=6)左邊的數(shù)都比它小，凡是k右邊的數(shù)都比它大：

如果i和j沒有碰頭的話，就遞加i找大的，還沒有，就再遞減j找小的，如此反復(fù)，不斷循環(huán)。注意判斷和尋找是同時進行的。

然后，對k兩邊的數(shù)據(jù)，再分組分別進行上述的過程，直到不能再分組為止。

注意：第一遍快速排序不會直接得到最終結(jié)果，只會把比k大和比k小的數(shù)分到k的兩邊。為了得到最后結(jié)果，需要再次對下標(biāo)2兩邊的數(shù)組分別執(zhí)行此步驟，然后再分解數(shù)組，直到數(shù)組不能再分解為止（只有一個數(shù)據(jù)），才能得到正確結(jié)果。

代碼實現(xiàn)：

#!/usr/bin/env python# -*- coding:utf-8 -*-# Author:luotianshuaiimport randomimport timedef quick_sort(array,start,end):    if start >= end:        return
    k = array[start]
    left_flag = start
    right_flag = end    while left_flag < right_flag:        '''
        left_flag = start 默認(rèn)為0
        right_flag = end 默認(rèn)為傳來的列表總長度
        當(dāng)left_flag 小與right_flag的時候成立,說明左右兩邊的小旗子還沒有碰頭(為相同的值)        '''
        #右邊旗子
        while left_flag < right_flag and array[right_flag] > k:#代表要繼續(xù)往左一移動小旗子
            right_flag -= 1        '''
        如果上面的循環(huán)停止說明找到右邊比左邊的值小的數(shù)了,需要進行替換        '''
        tmp = array[left_flag]
        array[left_flag] = array[right_flag]
        array[right_flag] = tmp        #左邊旗子
        while left_flag < right_flag and array[left_flag] <= k:            #如果沒有找到比當(dāng)前的值大的,left_flag 就+=1
            left_flag += 1        '''
        如果上面的循環(huán)停止說明找到當(dāng)前段左邊比右邊大的值,進行替換        '''
        tmp = array[left_flag]
        array[left_flag] = array[right_flag]
        array[right_flag] = tmp    #進行遞歸把問題分半
    quick_sort(array,start,left_flag-1)
    quick_sort(array,left_flag+1,end)if __name__ == '__main__':
    array = []  # [69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619]
    start_time = time.time()    for i in range(50000):
        array.append(random.randrange(1000000))
    quick_sort(array,0,len(array)-1)
    end_time = time.time()    print(array)    print(start_time,end_time)
    cost_time = end_time - start_time    print('Cost time is :%d' % cost_time)