def quick_sort(a):
if len(a) < 2:
return a
prv = a[0]
left = [x for x in a[1:] if x <= prv]
right = [x for x in a[1:] if x > prv]
return quick_sort(left)+[prv]+quick_sort(right)
#第一种代码简单，但是需要额外占用空间，空间复杂度高！
def quicksort(a,begin,end):
if begin<end:#递归的时候quicksort(a,right+1,end)可能会导致数组index溢出
prv = a[begin]
left = begin+1
right = end
while left <= right:#当left>right时停止循环，此时将prv与right的位置交换
while left <= right and a[right] > prv:
right-=1
while left <= right and a[left] <= prv:
left+=1
if left > right:
break
else:
a[left],a[right] = a[right],a[left]
a[right],a[begin] = a[begin],a[right]
quicksort(a,begin,right-1)
quicksort(a,right+1,end)
if __name__ == "__main__":
a = [1,8,8,0,5,1,9,3,7,6,6]
print(quick_sort(a))
b = [1,5,0,6,5,2,5,3,2,3]
quicksort(b,0,len(b)-1)
print(b)
c = [1232,43,13,4,124,54,7678,87,674,522,23]
quicksort(c,0,len(c)-1)
print(c)
d = [124,13,234,436,565,3466,5673,54,46]
quicksort(d,0,len(d)-1)
print(d)
e = [1321,435,12,3534,6,5768,7,789,7456,3]
quicksort(e,0,len(e)-1)
print(e)
快排(python)
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 算法可视化网站推荐---->visualgo 0.面试题中的排序算法 一些排序算法可能在工作中用的会比较少，但是面...
