上海土地建设官方网站,做网站有哪个软件好,甘孜热门抖音代运营,wordpress系统通知邮箱快速排序#xff1a;
学习快速排序#xff0c;要先复习下递归#xff1a;
递归的2个条件#xff1a;
1. 函数自己调用自己
2.有一个退出的条件
练习#xff1a;基于递归下一个函数#xff0c;计算n#xff01;并且求出当n等于10的值。
n#xff01;n * n-1*…..*1
#enc…快速排序
学习快速排序要先复习下递归
递归的2个条件
1. 函数自己调用自己
2.有一个退出的条件
练习基于递归下一个函数计算n并且求出当n等于10的值。
nn * n-1*…..*1
#enconding utf-8
def func(n):
if n1:
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是针对最小数刚好在最后一位的极端情况
初始值j0 j控制遍历数组的下标。
用j去和21比较如果大于21则空过不处理如果小于21i要加1把i和j指向的元素交换位置
手工排序
i-1 j0
取出12,1221-à i10i和j指向的元素交换位置此时ij0都是指向lista[0];j
12 23 3 4 56 21
i0j1
取出23,21 2321,空过
12 23 3 4 56 21
i0 j2
取出3,21 321- i11;i和j对应元素位置交换,lista[1],lista[2]
12 3 23 4 56 21
i1 j3
取出421,i12; i和j对应元素位置交换
12 3 4 23 56 21
i1;j4
取出5621;空过
12 3 4 23 56 21
把下标i1的元素和最后一个元素交换位置
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]
i1
lista[i],lista[j] lista[j],lista[i]
else:
pass
lista[eIndex],lista[i1] lista[i1],lista[eIndex]
return i1
def qSort(listb,sIndex,eIndex):
if sIndex eIndex: #如果开始位置大于等于起始位置返回
return
middle pathSort(listb,sIndex,eIndex)
#递归调用左子列表
qSort(listb,sIndex,middle-1)
#递归调用右子列表
qSort(listb,middle1,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:
i1
lista[i],lista[j] lista[j],lista[i]
else:
pass
lista[eIndex],lista[i1] lista[i1],lista[eIndex]
return i1
def qSort(listb,sIndex,eIndex):
if sIndex eIndex: #如果开始位置大于等于起始位置返回
return
middle pathSort(listb,sIndex,eIndex)
#递归调用左子列表
qSort(listb,sIndex,middle-1)
#递归调用右子列表
qSort(listb,middle1,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次
123….n-1 n^2/2
时间复杂度为Onlogn
平均情况
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^(i1)-2-I n
i1 ~ logn
I ~ logn
log(n-x)
最终时间复杂度为 Onlogn
