快速排序：
学习快速排序，要先复习下递归：
递归的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]<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])
变形练习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）
