首页 > 代码库 > python 冒泡排序与快速排序 遇到的错误与问题
python 冒泡排序与快速排序 遇到的错误与问题
今天看了兄弟连php里面的冒泡排序与快速排序，想了下应该可以用python实现。
冒泡排序函数：
def mysort(x):
len1 = len(x)
for i in range(len1-1,0,-1):
for j in range(0,i):
if x[j]>x[j+1]:
x[j],x[j+1]=x[j+1],x[j]
return x
第三行代码，是让i的值9到1，因为冒泡排序是大的数往后冒，当第二次循环时，最大的数已经在最后了，所以不需要在比较一次。
同理，第三次，只要让其比较到len1-2 ,第四次，比较到len1-1。
这样循环次数可以减少一半。
python支持直接交换列表值，这点也比较方便。
快速排序函数：
def qsort(x):
if (x == []) :
return []
len1 = len(x)
left = []
right = []
key = x[0]
for i in range(1,len1):
if(x[i]<=key):
left.append(x[i])
else:
right.append(x[i])
left = qsort(left)
right = qsort(right)
return left + [key] + right
快速排序的先有一个比较值key，这里取列表中的第一个值。让列表中的其他值与其比较。
如果小于它就放在right列表中，
如果大于它就放在left列表中。
然后递归。（对递归也不是很理解。只知道函数本身自己调用自己。）
最后将left、比较值key（需要转换成列表类型）、right连接在一起即可。
出现了一个错误：
RuntimeError: maximum recursion depth exceeded while calling a Python object
查询得知：
原来在python里面，递归函数的最大深度是999。超过这个深度就会报错。
我们只要在代码前面加上
import sys sys.setrecursionlimit(1000000)
设置成1000000即可解决。
最后的代码以及测试效率：
#!usr/bin/env python
#!coding=utf-8
__author__ = ‘zhengjim‘
import time
import random
import sys
sys.setrecursionlimit(1000000)
def mysort(x):
len1 = len(x)
for i in range(len1-1,0,-1):
for j in range(0,i):
if x[j]>x[j+1]:
x[j],x[j+1]=x[j+1],x[j]
return x
def qsort(x):
if (x == []) :
return []
len1 = len(x)
left = []
right = []
key = x[0]
for i in range(1,len1):
if(x[i]<=key):
left.append(x[i])
else:
right.append(x[i])
left = qsort(left)
right = qsort(right)
return left + [key] + right
if __name__ == ‘__main__‘:
x=[]
for i in range(1000000):
j = random.randint(1,10000)
x.append(j)
start = time.clock()
qsort(x) # 改变函数，比较效率
end =time.clock()
print ‘%f‘ % (end -start)
定义了一个1000000的乱序列表。
实验结果：
# 冒泡排序 跑了5分钟以上
# 快速排序 12.017942
#系统函数 0.428260
python 冒泡排序与快速排序 遇到的错误与问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。