正文
python实现排序算法一：快速排序
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
##快速排序算法
##基本思想：分治法，将数组分为大于和小于该值的两部分数据，然后在两部分数据中进行递归排序，直到只有一个数据结束
## step1: 取数组第一个元素为key值，设置两个变量，i = 0, j = len(a) - 1
## step2: j从后面开始遍历，遇到小于key的值，则a[i] = a[j]
## step3: i从前面开始遍历，遇到大于key的值，则a[j] = a[i]
## step4: 对两部分数据递归查找
代码如下：
def quicksort(a, m, n):
key = a[m]
i = m
j = n
while i < j:
while a[j] >= key and i < j:
j -= 1
if i < j:
a[i] = a[j]
i += 1
while a[i] <= key and i < j:
i += 1
if i < j:
a[j] = a[i]
j -= 1
a[i] = key
if m < i - 1:
quicksort(a, m, i - 1)
if n > j + 1:
quicksort(a, j + 1, n) if __name__ == '__main__':
b = [1, 22, 90, 4, 65, 3, 73, 8]
print(b)
length = len(b)
quicksort(b, 0, length - 1)
print(b)
在网上看到另一个很简单的方法，在这里补充一下吧
def qsort(seq):
if seq==[]:
return []
else:
pivot=seq[0]
lesser=qsort([x for x in seq[1:] if x<pivot])
greater=qsort([x for x in seq[1:] if x>=pivot])
return lesser+[pivot]+greater if __name__=='__main__':
seq=[5,6,78,9,0,-1,2,3,-65,12]
print(qsort(seq))
