快速排序：

學習快速排序，要先復習下遞歸：

遞歸的2個條件：

1. 函數自己調用自己

2.有一個退出的條件

練習：基于遞歸下一個函數，計算n！并且求出當n等于10的值。

n！=n * n-1*…..*1

#enconding = utf-8

def func(n):

if n<=1:

return 1

else:

return n*func(n-1)

print func(10)

結果：3628800

快速排序：也是基于遞歸的思想

核心思想：對于一個數組 12 23 3 4 56 21

快排是從里面隨機選擇一個數，如21，把所有小于這個數字的排在它的左邊，把所有大于它的數排在右邊。

用指針指明位置，遍歷數組：j-> 0到4

用i表示下標i左邊的都是小于21的，包括下標i

初始值 i=-1 -1是針對最小數剛好在最后一位的極端情況

初始值j=0 ，j控制遍歷數組的下標。

用j去和21比較，如果大于21，則空過不處理；如果小于21：i要加1，把i和j指向的元素交換位置

手工排序：

i=-1 j=0

取出12,12<21-à i+1=0；i和j指向的元素交換位置，此時i=j=0，都是指向lista[0];j++

12 23 3 4 56 21

i=0，j=1

取出23,21 23>21,空過

12 23 3 4 56 21

i=0 ，j=2

取出3,21， 3<21-> i+1=1;i和j對應元素位置交換,lista[1],lista[2] =

12 3 23 4 56 21

i=1 j=3

取出4<21,i+1=2; i和j對應元素位置交換

12 3 4 23 56 21

i=1;j=4

取出56>21;空過

12 3 4 23 56 21

把下標i+1的元素和最后一個元素交換位置

12 3 4 21 56 23

這樣，就完成了第一輪的排序。

為什么要選擇最后一個數字呢？

很容易找到。其實選擇哪一個最后的結果都是一樣的。因此為了簡單我們直接就取的最后一個數作為基準數字。

下面，我們來寫出12 3 4 以及右子列表56 23快排一次后的結果

左： 3 4 12

右：23 56

快排程序：

1.對于listx調用快排

2.對于listx的左子列表12 3 4進行快排，對于listx的右子列表56 23進行快排

3.直到列表只有一個元素的時候，退出

#enconding = utf-8

def Quick_Sort(lista):

def pathSort(lista,sIndex,eIndex):#第一重排序

flag = lista[eIndex]

i = sIndex - 1

for j in xrange(sIndex,eIndex):

if lista[j]

i+=1

lista[i],lista[j] = lista[j],lista[i]

else:

pass

lista[eIndex],lista[i+1] = lista[i+1],lista[eIndex]

return i+1

def qSort(listb,sIndex,eIndex):

if sIndex >= eIndex: #如果開始位置大于等于起始位置，返回

return

middle = pathSort(listb,sIndex,eIndex)

#遞歸調用左子列表

qSort(listb,sIndex,middle-1)

#遞歸調用右子列表

qSort(listb,middle+1,eIndex)

qSort(lista,0,len(lista)-1)

return lista

if __name__ == '__main__':

print Quick_Sort([12,3,4,21,56,23])

變形練習1：修改成從大到小排列。

#enconding = utf-8

def Quick_Sort(lista):

def pathSort(lista,sIndex,eIndex):#第一重排序

flag = lista[eIndex]

i = sIndex - 1

for j in xrange(sIndex,eIndex):

if lista[j]>flag:

i+=1

lista[i],lista[j] = lista[j],lista[i]

else:

pass

lista[eIndex],lista[i+1] = lista[i+1],lista[eIndex]

return i+1

def qSort(listb,sIndex,eIndex):

if sIndex >= eIndex: #如果開始位置大于等于起始位置，返回

return

middle = pathSort(listb,sIndex,eIndex)

#遞歸調用左子列表

qSort(listb,sIndex,middle-1)

#遞歸調用右子列表

qSort(listb,middle+1,eIndex)

qSort(lista,0,len(lista)-1)

return lista

if __name__ == '__main__':

print Quick_Sort([12,3,4,21,56,23])

時間復雜度：

第一輪：做完快排后發現基準數是最大的一個，我們比較了n-1次，最后一個

第二輪：n-2次

第三輪：n-3次

…

第n-1輪：1次

1+2+3….+n-1 = n^2/2

時間復雜度為O（nlogn）

平均情況：

n

第一輪：n-1，排列出2個列表，確定了1個結點的位置

第二輪：n-3，排列出4個列表，確定了3個結點的位置

第三輪：n-7，排列出8個列表，確定了7個結點的位置

第四輪：n-15，排列 出16個列表，確定了15個結點的位置

…..

平均比較次數n-x

2^i-1

總共需要多少輪，才能完成快排？

2^1 + 2^2 +…..2^i-I = n

2*(1-2^i)/1 -2 –I =n

2^(i+1)-2-I =n

i+1 ~ logn

I ~ logn

log(n-x)

最終時間復雜度為 O（nlogn）