一、常見的內(nèi)置函數(shù)

1. 查看內(nèi)置函數(shù)：

>>> print(dir(__builtins__))
>>> li = dir(__builtins__)
>>> li.index('abs')     #80
>>> li[80:]
['abs', 'all', 'any', 'ascii', 'bin', 'bool', 'bytearray', 'bytes', 'callable', 'chr', 'classmethod', 'compile', 'complex', 'copyright', 'credits', 'delattr', 'dict', 'dir', 'divmod', 'enumerate', 'eval', 'exec', 'exit', 'filter', 'float', 'format', 'frozenset', 'getattr', 'globals', 'hasattr', 'hash', 'help', 'hex', 'id', 'input', 'int', 'isinstance', 'issubclass', 'iter', 'len', 'license', 'list', 'locals', 'map', 'max', 'memoryview', 'min', 'next', 'object', 'oct', 'open', 'ord', 'pow', 'print', 'property', 'quit', 'range', 'repr', 'reversed', 'round', 'set', 'setattr', 'slice', 'sorted', 'staticmethod', 'str', 'sum', 'super', 'tuple', 'type', 'vars', 'zip']
>>> len(li[80:])    #72

2. 常見函數(shù)：

len 求長度
min 求最小值
max 求最大值
sorted  排序
reversed 反向
sum  求和

>>> help(sum)   #求和一個可迭代對象，start從哪開始。
Help on built-in function sum in module builtins:
sum(iterable, start=0, /)
    Return the sum of a 'start' value (default: 0) plus an iterable of numbers
    
    When the iterable is empty, return the start value.
    This function is intended specifically for use with numeric values and may
    reject non-numeric types.
>>> sum([1,2,3,4])  10
>>> sum([1,2,3,4],10)   20

3. 進(jìn)制轉(zhuǎn)換函數(shù):

4. 補充：

(1) enumerate()

??enumerate(iterable[, start]) -> iterator for index, value of iterable
??返回一個可以枚舉的對象(一個元組(index, value))

>>> enumerate([1,2,3,4])        # <enumerate object at 0x00000193373611F8>
>>> list(enumerate([1,2,3,4]))          #[(0, 1), (1, 2), (2, 3), (3, 4)]
>>> list(enumerate(['a','b','c']))      #[(0, 'a'), (1, 'b'), (2, 'c')]
>>> list(enumerate(['a','b','c'],5))    #[(5, 'a'), (6, 'b'), (7, 'c')]
>>> list(enumerate({'a','b','c'},5))    #[(5, 'a'), (6, 'c'), (7, 'b')]
>>> list(enumerate({'a':1,'b':1,'c':1},5))  #[(5, 'a'), (6, 'b'), (7, 'c')]

(2) filter()

??filter(function or None, iterable) --> filter object
??過濾器 將可迭代對象經(jīng)過函數(shù)的過濾再返回一個filter object
??參數(shù)(篩選函數(shù)，篩選對象)

>>> filter(lambda x:x>2,[1,2,3,4,5])    
    #<filter object at 0x0000019337348EB8>
>>> list(filter(lambda x:x>2,[1,2,3,4,5])   # [3, 4, 5]
>>> list(filter(fun,[1,2,3,4,5])    #這里只是放一個函數(shù)體
>>> list(filter(None,[1,2,3,4,5]))  #[1, 2, 3, 4, 5]

(3) map()

??<b><i>map(func, *iterables) --> map object</i></b>
??加工。
??對于參數(shù)iterable中的每個元素都應(yīng)用fuction函數(shù)，并返回一個map對象

>>> map(str,[1,2,3])    #<map object at 0x0000019337348D68>
>>> list(map(str,[1,2,3]))  #['1', '2', '3']

(4) zip()

??zip(iter1 [,iter2 [...]]) --> zip object
??將對象逐一配對

>>> zip([1,2,3])    #<zip object at 0x000001933733F808>
>>> list(zip([1,2,3]))  #[(1,), (2,), (3,)]
>>> list(zip([1,2,3],[11,22,33]))   #[(1, 11), (2, 22), (3, 33)]
>>> list(zip([1,2,3],[11,22,33],'a'))   #[(1, 11, 'a')]后面兩個沒有配了
>>> list(zip([1,2,3],[11,22,33],'aaaaa'))   
    #[(1, 11, 'a'), (2, 22, 'a'), (3, 33, 'a')] 

??配對的參數(shù)可多不可少

二、作用域

??變量到底是什么呢？可將其視為指向值的名稱。因此，執(zhí)行賦值語句x=1后，名稱x指向值1。這幾乎與使用字典一樣(字典中的鍵指向值)，只是你使用的是"看不見"的字典。實際上，這種解釋已經(jīng)離真相不遠(yuǎn)。有一個名為vars的內(nèi)置函數(shù)，它返回這個不可見的字典：

>>> x = 1
>>> scope = vars()
>>> scope['x']  #1

??警告：一般而言，不應(yīng)修改vars返回的字典，因為根據(jù)Python官方文檔的說法，這樣做的結(jié)果是不確定的。
??這種"看不見的字典"稱為命名空間或作用域。在Python中，程序的變量并不是在任何位置都可以訪問的，訪問權(quán)限決定于這個變量是在哪里賦值的，代碼中變量被賦值的位置決定哪些范圍的對象可以訪問這個變量，這個范圍就是命名空間。
??那么有多少個命名空間呢？除全局作用域外，每個函數(shù)調(diào)用都將創(chuàng)建一個，函數(shù)中定義的變量等可以認(rèn)為都是存儲在這個命名空間中的，這些變量的調(diào)用不會影響到全局變量。

1. 局部變量與全局變量

??變量的作用域決定哪一部分程序可以訪問特定的變量名稱。

>>> x=1   #全局
>>> def fun1():
        y = 2 # 局部
        print(x,y)
>>> fun1()  #1 2

??全局能夠進(jìn)入局部變量。

>>> x = 1
>>> def foo(): x = 42
>>> foo()
>>> x   #1

??在這里，函數(shù)foo修改了變量x，但當(dāng)你最終查看時，他根本沒變。這是因為調(diào)用foo時創(chuàng)建了一個新的命名空間，供foo中的代碼塊使用。賦值語句x=42是在這個內(nèi)部作用域(局部命名空間)中執(zhí)行的，不影響外部(全局)作用域內(nèi)的x。
??在函數(shù)內(nèi)使用的變量只能被函數(shù)內(nèi)部引用，不能再函數(shù)外引用，這個變量的作用域是局部的，也稱為局部變量。
??在函數(shù)外，一段代碼最開始賦值的變量可以被多個函數(shù)引用，這就是全局變量。
??全局變量可以在整個程序范圍內(nèi)訪問。參數(shù)類似于局部變量，因此參數(shù)與全局變量同名不會有任何問題。
??函數(shù)中使用某個變量時，如果參數(shù)中的局部變量與全局變量同名，默認(rèn)使用局部變量。
??如果只是想讀取這種變量的值(不去重新關(guān)聯(lián)它)，通常不會有任何問題。

>>> def combine(parameter): print(parameter + external)
>>> external = 'berry'
>>> combine('Shurb')    #Shrubbery

??警告：像這樣訪問全局變量是眾多bug的根源。務(wù)必慎用全局變量。
??遮蓋問題：
??如果有一個局部變量或參數(shù)與你要訪問的全局變量同名，就無法直接訪問全局變量，因為它被局部變量遮住了。
??例如，在前面的示例中，如果有一個名為parameter的全局變量，就無法在函數(shù)combine中訪問它，因為有一個與之同名的參數(shù)。然而，必要時可使用globals()['parameter']來訪問它。

>>> def combine(parameter): print(parameter + globals()['parameter'])
>>> external = 'berry'
>>> combine('Shurb')    #Shrubbery

??重新關(guān)聯(lián)全局變量(使其指向新值)是另一碼事。在函數(shù)內(nèi)部給變量賦值時，該變量默認(rèn)為局部變量，除非你明確告訴Python它是全局變量。那么如何告知呢？
??如果你想指明使用全局變量，可以使用globals()['全局變量名']，或者global 變量名。這個函數(shù)返回一個包含全局變量的字典。(locals返回一個包含局部變量的字典。)

>>> def fun2():
    a = 1
    print(a)
>>> a   #NameError: name 'a' is not defined
>>> fun2()  #1
>>> a   #NameError: name 'a' is not defined

??局部變量不能進(jìn)入全局,

>>> x = 1
>>> def change_global():
        global x
        x = x + 1
>>> change_global()
>>> x   #2

??如果要進(jìn)，也要global。

2. 作用域嵌套

??另外，Python是支持函數(shù)嵌套使用的,即可將一個函數(shù)放在另一個函數(shù)內(nèi)，如下所示：

>>> def foo():
        def bar():
            print('hello')
        bar()

??嵌套的用處不大，但有一個很突出的用途，使用一個函數(shù)來創(chuàng)建另一個函數(shù)。這意味著可像下面這樣編寫函數(shù)：

>>> def multiplier(factor):
        def multiplyByFactor(number):
            return number * factor
        return multiplyByFactor     #返回函數(shù)體
>>> multiplier()    
    # <function multiplier.<locals>.multiplyByFactor at 0x0000019337373E18>

??在這里，一個函數(shù)位于另一個函數(shù)中，且外面的函數(shù)返回里層的函數(shù)。也就是返回一個函數(shù)體，而不是調(diào)用它。重要的是，返回的函數(shù)能夠訪問其定義所在的作用域。換而言之，它攜帶著自己所在的環(huán)境(和相關(guān)的局部變量)。
??每當(dāng)外部函數(shù)被調(diào)用時，都將重新定義內(nèi)部的函數(shù)，而變量factor的值也可能不同。由于Python的嵌套作用域，可在內(nèi)部函數(shù)中訪問這個來自外部局部作用域(multiplier)的變量，如下所示：

>>> double = multiplier(2)
>>> double(5)   #10
>>> trible = multiplier(3)
>>> trible(3)   #9
>>> multiplier(5)(4)    #20

??像multiplyByFactor這樣存儲其所在作用域的函數(shù)成為閉包。倆個函數(shù) 嵌套。

>>> def test1():
        a = 1
        print('局部外層')
        # test2()不能放在這里，因為函數(shù)還沒有定義
        def test2():
            b = 2
            a += 1
            print('局部內(nèi)層', a,b)
        test2()

??打印一行，然后報錯。局部外層能進(jìn)入局部里層,但是不能修改。通常，不能給外部作用域內(nèi)的變量賦值。

>>> def test1():
    a = 1
    print('局部外層')
    # test2()不能放在這里，因為函數(shù)還沒有定義
    def test2():
        b = 2
        nonlocal a
        a += 1
        print('局部內(nèi)層', a,b)
    test2()

??但如果一定要這樣做，可使用關(guān)鍵字nonlocal。這個關(guān)鍵字的用法和global很像，讓你能夠給外部作用域(非全局作用域)內(nèi)的變量賦值。(作用于局部)。
??使用global情況：

• 全局變量可以在函數(shù)內(nèi)部訪問，但是不能改變
• 如果在函數(shù)內(nèi)部想修改全局變量，可以用global來修飾變量
• 局部變量只能在局部進(jìn)行訪問修改。
• 如果在函數(shù)外部，想訪問局部變量，也可以用global，將局部變量聲明為全局變量

??使用nonlocal的情況：

• 當(dāng)里層局部，需要修改外層局部時，需要使用nonlocal。 (如嵌套函數(shù))

3. 回調(diào)函數(shù)

??倆個函數(shù) 不嵌套

>>> def test12():
        print('我是第一個函數(shù)')
>>> def fun12(a):
        a()
        print('我是老二')
>>> fun(test1)  
    # 我是第一個函數(shù)
    # 我是老二

??閉包加回調(diào)函數(shù)組成裝飾器。

三、遞歸

??遞歸意味著引用自身，即自己調(diào)用自己。例如：

>>> def recursion():
        return recursion()

??這個函數(shù)中的遞歸稱為無窮遞歸，因為它從理論上說永遠(yuǎn)不會結(jié)束。這類遞歸稱作無窮遞歸，實際操作一會兒程序就崩潰了。因為每次調(diào)用函數(shù)都會用掉一點內(nèi)存，當(dāng)內(nèi)存空間被占滿，程序就會報異常。
??如果一個函數(shù)在內(nèi)部調(diào)用自身，這個函數(shù)就稱作遞歸函數(shù)。

??有用的遞歸函數(shù)通常包含下面兩部分：

• 基線條件(針對最小的問題)：滿足這種條件時函數(shù)將直接返回一個值。（這樣就避免了無限調(diào)用的可能）
• 遞歸條件：包含一個或多個調(diào)用，這些調(diào)用旨在解決問題的一部分。

??這里的關(guān)鍵是，通過將問題分解為較小的部分，可避免遞歸沒完沒了，因為問題終將被分解成基線條件可以解決的最小問題。
??其實函數(shù)每次被調(diào)用時都會創(chuàng)建一個新命名空間，也就是當(dāng)函數(shù)調(diào)用自身時，實際上運行的是兩個不同的函數(shù)(也可以說一個函數(shù)具有兩個不同的命名空間)。

遞歸的核心：

1. 遞歸推導(dǎo)式
2. 遞歸終止條件

1. 兩個經(jīng)典案例：階乘和冪

??階乘：當(dāng)然，你可以用循環(huán)的思想來寫，像下面這樣

>>> def factorial(n):
    result = n
    for i in range(1,n):
        result *= i
    return result

??它是這樣做的：首先將result設(shè)置為n，再將其依次乘以1到n-1的每個數(shù)字，最后返回result。關(guān)于階乘的數(shù)學(xué)定義為：1的階乘為1。對于大于1的數(shù)字n其階乘為n-1的階乘再乘以n。
這里我們換一種思路，用遞歸來實現(xiàn)：

>>> def factorial(n):
    if n == 1:      #基線條件，滿足即退出函數(shù)
        return 1
    else:
        return  n * factorial(n – 1)

??我們再來定義冪的運算(就是和內(nèi)置函數(shù)pow一樣的效果)。冪運算的定義是power(x,n)(x的n次冪)是將數(shù)字x自乘n-1次的結(jié)果，即將n個x相乘的結(jié)果。

>>> def power(x, n):
        result = 1
        for i in range(n):
            result *= x
        return result

??遞歸式定義為對于任何數(shù)字x，power(x,0)都為1。n>0時，power(x,n)為power(x,n-1)與x的乘積。

>>> def power(x, n):
    if n == 0:
        return  1
    else:
        return x * power(x, n-1)

??當(dāng)然，你可以明顯的看到，遞歸大部分情況是可以用循環(huán)代替的，而且循環(huán)在時間復(fù)雜度可能更好一點，但是當(dāng)你掌握了遞歸，你就會愛上這種簡潔的表達(dá)方式。
??提示：如果函數(shù)或算法復(fù)雜難懂，在實現(xiàn)前用自己的話進(jìn)行明確的定義將大有裨益。以這種"準(zhǔn)編程語言"編寫的程序通常稱為偽代碼。
??在大多數(shù)情況下，使用循環(huán)的效率可能更高。然而，在很多情況下，使用遞歸的可讀性更高，且有時要高得多。遞歸函數(shù)的優(yōu)點是定義簡單，邏輯清晰。

>>> def fact(n):
        if n == 1:
            return 1
        return n * fact(n – 1)

??使用遞歸函數(shù)需要注意防止棧溢出。在計算機(jī)中，函數(shù)調(diào)用是通過棧(stack)這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的。每當(dāng)進(jìn)入一個函數(shù)調(diào)用，棧就會加一層棧幀；每當(dāng)函數(shù)返回，棧就會減一層棧幀。由于棧的大小不是無限的，因此遞歸調(diào)用的次數(shù)過多會導(dǎo)致棧溢出。

>>> fact(1000)
Traceback (most recent call last):
  File "<pyshell#15>", line 1, in <module>
    fact(1000)
  File "<pyshell#13>", line 4, in fact
    return n * fact(n-1)
  File "<pyshell#13>", line 4, in fact
    return n * fact(n-1)
  File "<pyshell#13>", line 4, in fact
    return n * fact(n-1)
  [Previous line repeated 989 more times]
  File "<pyshell#13>", line 2, in fact
    if n == 1:
RecursionError: maximum recursion depth exceeded in comparison

??異常提示超過最大遞歸深度。
??解決遞歸調(diào)用棧溢出的方法是通過尾遞歸優(yōu)化，事實上尾遞歸和循環(huán)的效果一樣，把循環(huán)看成是一種特殊尾遞歸函數(shù)也可以。
??尾遞歸是指在函數(shù)返回時調(diào)用函數(shù)本身，并且return語句不能包含表達(dá)式。這樣，編譯器或解釋器就可以對尾遞歸進(jìn)行優(yōu)化，使遞歸本身無論調(diào)用多少次都只占用一個棧幀，從而避免棧溢出的情況。

>>> def fact(n):
        return fact_iter(n,1)
>>> def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)

??可以看到，return fact_iter(num - 1, num * product)僅返回遞歸函數(shù)本身， num - 1和num * product在函數(shù)調(diào)用前就會被計算，不影響函數(shù)調(diào)用。
??由操作結(jié)果看到，調(diào)用尾遞歸時如果做了優(yōu)化，棧就不會增長，因此無論多少次調(diào)用都不會導(dǎo)致棧溢出。

2. 另一個經(jīng)典案例：二分查找

??例如，對方心里想著一個1-100的數(shù)字，你必須猜出是哪個。實際上只需要猜7次。首先問：這個數(shù)字大于50嗎？如果答案是肯定的，再問：這個數(shù)字大于75嗎？不斷將可能的區(qū)間減半，知道猜對為止。你無需過多地思考就能成功。
??這里的關(guān)鍵是，這種算法自然而然地引出了遞歸式定義和實現(xiàn)。先來回顧一下定義，確保知道該如何做。

• 如果上限和下限相同，就說明它們都指向數(shù)字所在的位置，因此將這個數(shù)字返回。
• 否則，找出區(qū)間的中間位置(上限和下限的平均值)，再確定數(shù)字在左半部分還是有半部分。然后繼續(xù)在數(shù)字所在的那部分中查找。

??在這個遞歸案例中，關(guān)鍵在于元素是經(jīng)過排序的。找出中間的元素后，只需將其與要查找的數(shù)字進(jìn)行比較即可。如果要查找的數(shù)字更大，肯定在右邊；如果更小，它必然在左邊。遞歸部分為"繼續(xù)在數(shù)字所在的那部分中查找"，因為查找方式與定義所指定的完全相同。(請注意，這種查找算法返回數(shù)字應(yīng)該在的位置。如果這個數(shù)字不在序列中，那么這個位置上的自然是另一個數(shù)字。)
??現(xiàn)在可以實現(xiàn)二分查找了。

>>> def search(sequence, number, lower=0, upper=None):
    if upper is None: upper = len(sequence) - 1
    if lower == upper:
        assert number == sequence[upper]
        return upper
    else:
        middle = (lower + upper) // 2
        if number > sequence[middle]:
            return search(sequence, number, middle + 1, upper)
        else:
            return search(sequence, number, lower, middle)

??提示：實際上，模塊bisect提供了標(biāo)準(zhǔn)的二分查找實現(xiàn)。

3. 函數(shù)式編程

??在Python中，通常不會如此倚重函數(shù)(而是創(chuàng)建自定義對象，這將在下一章詳細(xì)介紹)，但完全可以這樣做。
??Python提供了一些有助于這種函數(shù)式編程的函數(shù)：map、filter和reduce。在較新的Python版本中，函數(shù)map和filter的用途并不大，應(yīng)該使用列表推導(dǎo)來替代它們。你可使用map將序列的所有元素傳遞給函數(shù)。

>>> list(map(str, range(10)))   #與[str(i)for i in range(10)]等價
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

??你可使用filter根據(jù)布爾函數(shù)的返回值對元素進(jìn)行過濾。

>>> def func(x):
        return x.isalnum()
>>> seq = ["foo", "x41", "?!", "***"]
>>> list(filter(func, seq)) #['foo', 'x41']

??就這個示例而言，如果轉(zhuǎn)而使用列表推導(dǎo)，就無需創(chuàng)建前述自定義函數(shù)。

>>> [x for x in seq if x.isalnum()] #['foo', 'x41']

??實際上，Python提供了一種名為lambda表達(dá)式的功能，讓你能夠創(chuàng)建內(nèi)嵌的簡單函數(shù)(主要供map、filter和reduce使用)

>>> filter(lambda x: x.isalnum(), seq)  #['foo', 'x41']

??然而，使用列表推導(dǎo)的可讀性不是更高嗎？
??要使用列表推導(dǎo)來替換函數(shù)reduce不那么容易，而這個函數(shù)提供的功能即便能用到，也用的不多。它使用指定的函數(shù)將序列的前兩個元素合二為一，再將結(jié)果與第3個元素合二為一，以此類推，直到處理完整個序列并得到一個結(jié)果。例如，如果你要將序列中的所有數(shù)相加，可結(jié)合使用reduce和lambda x,y:x+y。

>>> numbers = [1,2,3,4]
>>> from functools import reduce
>>> reduce(lambda x,y: x+y,numbers) #10

??就這個示例而言，還不如使用內(nèi)置函數(shù)sum。

四、匿名函數(shù)

??匿名函數(shù)就是不再使用def語句這樣的標(biāo)準(zhǔn)形式定義一個函數(shù)。
??Python使用lambda創(chuàng)建匿名函數(shù)。lambda只是表達(dá)式，函數(shù)體比def簡單很多。
??lambda的主體是一個表達(dá)式，而不是一個代碼塊，僅能在lambda表達(dá)式中封裝優(yōu)先的邏輯。??lambda函數(shù)擁有自己的命名空間，不能訪問自有參數(shù)列表之外或全局命名空間的參數(shù)。
??lambda函數(shù)的語法只包含一個語句：lambda [args1[,args2,…argn]]:expression
??看一個求兩個數(shù)和的示例。

>>> def func(x,y):
        return x+y
>>> lambda x,y:x+y

??可以看出，使用lambda表達(dá)編寫的代碼比使用def語句少。
??比如求一個列表中大于3的元素，通過函數(shù)式編程實現(xiàn)，運用filter。

>>> def func(x):
        return x>3
>>> f_list = filter(func,[1,2,3,4,5])
>>> print([item for item in f_list])

??如果使用匿名函數(shù)，

>>> print([item for item in filter(lambda x:x>3,[1,2,3,4,5])

??從上面的操作可以看出，lambda一般應(yīng)用于函數(shù)式編程，代碼簡介，常和filter等函數(shù)結(jié)合使用。
??我們對lambda進(jìn)行解析。在表達(dá)式中
??x為lambda函數(shù)的一個參數(shù)，:為分割符，x>3為返回值，item for item in filter是filter函數(shù)的取值方式。

一般情況多考慮使用匿名函數(shù)：

• 程序一次性使用、不需要定義函數(shù)名時，用匿名函數(shù)可以節(jié)省內(nèi)存中變量定義空間。
• 如果想讓程序更加簡潔，使用匿名函數(shù)就可以做到。

匿名函數(shù)有3個規(guī)則要記住：

1. 一般有一行表達(dá)式，必須有返回值
2. 不能有return
3. 可以沒有參數(shù)，也可以有一個或多個參數(shù)

??下面來看幾個匿名函數(shù)的示例。
無參匿名函數(shù)：

>>> t = lambda :True
>>> t()     #True

帶參數(shù)匿名函數(shù)

>>> lambda x : x**3
>>> lambda x,y,z : x+y+z
>>> lambda x,y=3 : x*y

匿名函數(shù)調(diào)用：

>>> c = lambda x,y,z : x*y*z    
>>> c(2,3,4)    #24

五、偏函數(shù)

??偏函數(shù)通過模塊functools被用戶調(diào)用。
??偏函數(shù)是將所要承載的函數(shù)作為partial()函數(shù)的第一個參數(shù)，原函數(shù)的各個參數(shù)一次作為partial()函數(shù)的后續(xù)參數(shù)，除非使用關(guān)鍵字參數(shù)。
??在這個例子里，將實現(xiàn)一個取余函數(shù)，取得整數(shù)100對不同數(shù)m的100%m的余數(shù)。

>>> from functools import partial
>>> def mod(n,m):
        return n%m
>>> mod_by_100 = partial(mod,100)
>>> print(mod(100,7)    #2
>>> print(mod_by_100(7))    #2

??由執(zhí)行結(jié)果看到，使用偏函數(shù)所需代碼量比自定義函數(shù)更少、更簡潔。

六、快速排序

??快速排序是一種分治排序算法。該算法首先選取一個劃分元素(pivot)；然后重排列表，將其劃分為3個部分，即left(小于劃分元素pivot的部分)，pivot、right(大于劃分元素pivot的部分)，此時劃分元素pivot已經(jīng)在列表的最終位置上；最后分別對left和right兩部分進(jìn)行遞歸排序。
??其中，劃分元素的選取直接影響快速排序算法的效率，通常選擇列表的第一個元素、中間元素或最后一個元素作為劃分元素，當(dāng)然也有更復(fù)雜的選擇方式。劃分過程根據(jù)劃分元素重排列表，是快速排序算法的關(guān)鍵所在。
??快速排序算法的優(yōu)點是原位排序(只使用很小的輔助棧)，平均時間復(fù)雜度為O(n log n)。快速排序算法的缺點是不穩(wěn)定，最壞情況下時間復(fù)雜度為O(n2)

>>> def quicksort(L):
    qsort(L, 0, len(L) - 1)

>>> def qsort(L, first, last):
    if first < last:
        split = partition(L, first, last)
        qsort(L, first, split - 1)
        qsort(L, split + 1, last)

>>> def partition(L, first, last):
    # 選取列表中的第一個元素作為劃分元素
    pivot = L[first]
    leftmark = first + 1
    rightmark = last
    while True:
        while L[leftmark] <= pivot:
            # 如果列表中存在與劃分元素相等的元素，讓它位于left部分
            # 以下檢測用于劃分元素pivot是列表中的最大元素時
            # 放置leftmark越界
            if leftmark == rightmark:
                break
            leftmark += 1
            while L[rightmark] > pivot:
                # 這里不需要檢測，劃分元素pivot是列表中的最小元素時
                # rightmark自動停在first處
                rightmark -= 1
            if leftmark < rightmark:
                # 此時，leftmark處的元素大于pivot
                # rightmark處的元素小于等于pivot，交換兩者
                L[leftmark], L[rightmark] = L[rightmark], L[leftmark]
            else:
                break
        # 交換first處的劃分元素與rightmark處的元素
        L[first], L[rightmark] = L[rightmark], L[first]
        # 返回劃分元素pivot的最終位置
        return rightmark
>>> num_list = [5,-4,6,3,7,11,1,2]
>>> quicksort(num_list)
>>> print(num_list)     #[-4, 1, 2, 3, 5, 7, 6, 11]