计算机十大经典算法(python版)之快速排序法
个人理解:快速排序法是通过在整个数据源中选择基准数据,并通过递归方式以基准数据为块内数据大小分界点,将整块数据不断分割为一个个小数据块。再将小数据块作同样处理,最终达到排序目的的一种算法。
用到的知识:递归
递归算法百度网址:https://baike.baidu.com/item/%E9%80%92%E5%BD%92%E7%AE%97%E6%B3%95/4323575?fr=aladdin
上代码
# 目标数据生成
import random
l=[]
i=0
while i<30:
l.append(random.randint(1,100))
i+=1
print('排序目标:',l)
# 快速排序,每次递归以范围内最左边的为基准
def run(l,i=0,j=29):
left=i
right=j
while True:
if left==right:
left-=1
right+=1
break
# 范围内从右向左挑小于基准的
for item in range(left,right):
if l[left] < l[right]:
l[right], l[left] = l[left], l[right]
left+=1
# 每变动一次都要检验,否则有一半的可能出现无限递归
if left == right:
left -= 1
right += 1
break
# 范围内从左往右挑大于基准的
for item in range(left,right):
if l[left] > l[right]:
l[right], l[left] = l[left], l[right]
right -= 1
# 向左递归
if i < left:
run(l,i,left)
# 向右递归
if j > right:
run(l,j,right)
return l
# 显示结果
print("排序结果:",ll)
我的运行结果
排序目标: [76, 71, 6, 100, 46, 55, 69, 18, 11, 3, 61, 44, 64, 67, 51, 25, 17, 92, 90, 60, 18, 40, 38, 86, 14, 85, 97, 27, 60, 44]
排序结果: [100, 97, 92, 90, 86, 85, 76, 71, 69, 67, 64, 61, 60, 60, 55, 51, 46, 44, 44, 40, 38, 27, 25, 18, 18, 17, 14, 11, 6, 3]
|