快速排序:
学习快速排序, 要先复习下递归:
递归的 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)
来源: http://www.bubuko.com/infodetail-2494860.html